Day 30, 18,22, 4Sum, Generate Parentheses

4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

 -----------------------------------------------------------------------------------------
O(n^3), solution based on 3sum
the efficiency of the best solution for m sum is O(n^(m-1)) 

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > result;
        if (num.size() < 4) {
            return result;
        }
        sort(num.begin(),num.end());
        for (int j=0;j<num.size()-3;j++) {
            int a = num[j];
            // 3sum
            for (int i=j+1;i<num.size()-2;i++) {
                int b = num[i];
                int left = i+1;
                int right = num.size() - 1;
                // 2sum
                while (left < right) {
                    int c = num[left];
                    int d = num[right];
                    int sum = a + b + c + d;
                    if (sum == target) {
                        vector<int> t = {a,b,c,d};
                        if (find(result.begin(), result.end(), t) == result.end()) {
                            result.push_back(t);
                        }
                        right--;
                        left++;
                    }else if (sum < target) {
                        left++;
                    }else {
                        right--;
                    }
                }
            }
        
        }
    }
};

Update on Sep-10-2014
Solution #2, similar to the update of 3sum

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > rt;
        if (num.size() < 4) {
            return rt;
        }
        sort(num.begin(), num.end());
        
        
        for (int first = 0; first < num.size() - 3; first++) {
            if (first > 0 && num[first] == num[first - 1]) {
                continue;
            }
            
            for (int second = first + 1; second < num.size() - 2; second++) {
                if (second > first + 1 && num[second] == num[second - 1]) {
                    continue;
                }   
                int left = second + 1;
                int right = num.size() - 1;
                while (left < right) {
                    int sum = num[first] + num[second] + num[left] + num[right];
                    if (sum == target) {
                        vector<int> v(4);
                        v[0] = num[first];
                        v[1] = num[second];
                        v[2] = num[left];
                        v[3] = num[right];
                        rt.push_back(v);
                        
                        while (num[left] == num[left + 1]) {
                            left++;
                        }
                        while (num[right] == num[right - 1]) {
                            right--;
                        }
                    }
                    
                    if (sum < target) {
                        left++;
                    }else {
                        right--;
                    }
                }
            }
        }
        
        return rt;
    }
};

Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
 -----------------------------------------------------------------
Solution #1 

class Solution {
public:
    vector<string> rec (int n, int total) {
        vector<string> ret;
        if (n == 1) {
            ret.push_back("(");
            return ret;
        }
        ret = rec(n-1,total);
        vector<string> retNew;
        for (int i=0;i<ret.size();i++) {
            // calculate the balance of the current string
            int bal = 0;
            for (int j=0;j<ret[i].length();j++) {
                if (ret[i][j] == '(') {
                    bal++;
                }else {
                    bal--;
                }
            }
            
            if (bal > 0) {
                string s = ret[i] + ')';
                retNew.push_back(s);
            }
            if (bal < (total-n)) {
                string s = ret[i] + '(';
                retNew.push_back(s);
            }           
        }
        return retNew;
    }

    vector<string> generateParenthesis(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return rec(2*n,2*n);
    }
};

Solution #2, similar algorithm, from internet

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    if (n>0) generator(ans, "", 0, 0, n);
    return ans;
}

void generator(vector<string> & ans, string s, int l, int r, int n) { 
    if (l == n) {
        ans.push_back(s.append(n-r, ')'));
        return;
    }
    generator(ans, s+'(', l+1, r, n);
    if (l>r) generator(ans, s+")", l, r+1, n);
}

Update on Sep-10-2014
Solution #3, re-factoried, increased readability

class Solution {
public:
    void rec(vector<string> &rt, string str, int left, int right, int n) {
        if (left == n && right == n) {
            rt.push_back(str);
        }
        
        if (left < n) {
            rec(rt,str + "(",left + 1, right, n);
        }
        if (right < left) {
            rec(rt,str + ")",left, right + 1, n);
        }
        
    }

    vector<string> generateParenthesis(int n) {
        vector<string> rt;
        rec(rt,"",0,0,n);
        return rt;
    }
};