Leetcode 22 : Generate Parentheses Solution

Problem Statement could be found @https://leetcode.com/problems/generate-parentheses/

Approach -

1.Take a char array of size 2*n.
2. At every value of n try putting '(' or ')'. Reduce count of open brackets and closed brackets
3. If both open brackets & close brackets count reduce to 0,then it means we have  got one combination
4. A condition to take care is - never count of open brackets is greater than close brackets as it would result in wrong code formation

Code Snippet-

class Solution {
public:
    vector<string> retVec;
   
    void helper(int open ,int close, int n, char *x,int index){
        if ((open == 0) && (close ==0)){
            retVec.push_back(x);
            return;
        }
        //results in wrong formation
        if (open > close){
            return;
        }
       
        if (open > 0){
            x[index] = '(';
            helper((open-1),close, n, x, index+1);
        }
       
        if (close > 0){
            x[index] = ')';
            helper(open,close-1, n, x, index+1);
        }
    }
   
    vector<string> generateParenthesis(int n) {
        char *ptr = new char[2*n+1];
        ptr[2*n] = 0;
        helper(n,n,n,ptr,0);
        return retVec;
    }
};

Leetcode 15 : 3Sum Solution

Problem Statement could be found @https://leetcode.com/problems/3sum/

Approach -
A brute force solution like below is simple
1. Fix one element and then find next 2 elements such that sum of 3 elements becomes zero
2. In a random shuffled array above point would be O(n*n*n)

We can try optimizing above
1. Let us try to sort the array first O(nlogn)
2. Now start from first  element (lets say i), pick (i+1)th element and last element. Sum of these 3 if zero then we have one solution. Otherwise, if it is less than zero, then increase (i+1) else decrease last.
3. Trying step 2 in a for loop would give us result but it would have duplicates
4. We can eliminate duplicates by few additional checks as in code below



Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> retVec;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
         
            int a =  nums[i];
            if (a >0){
                break;
            }else {
                while((i<nums.size()) && (i>0) && (nums[i] == nums[i-1] )){
                    i++;
                }
            }
            a = nums[i];
            int j = i+1;
            int k = nums.size()-1;
           
            while(j <k){
                int comp = a + nums[j] + nums[k];
                if (comp == 0){
                    vector<int> v;
                    v.push_back(a);
                    v.push_back(nums[j]);
                    v.push_back(nums[k]);
                    retVec.push_back(v);
                    j++;
                    k--;
                    while ( (j <k) &&(nums[j] == nums[j-1]) ){
                        j++;
                    }
                    while ( (j <k) &&(nums[k] == nums[k+1]) ){
                        k--;
                    }
                 
                }
                if (comp < 0){
                    j++;
                }
                if (comp>0){
                    k--;
                }
               
            }
        }
        return retVec;
    }
};