Generate Parentheses. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

generateParenthesis.cc

class Solution {
public:
    // use backtracking
    void _genParen(int lCount, int rCount, int idx, string &str, vector<string> & res)
    {
       if(lCount < 0 || rCount < lCount)
            return;
        else if(0 == lCount && 0 == rCount)
        {
            res.push_back(str);
        }else
        {
            if(lCount)
            {
                str[idx] = '(';
                _genParen(lCount-1, rCount, idx+1, str, res);
            }
            
            if(rCount > lCount)
            {
                str[idx] =  ')';
                _genParen(lCount, rCount-1, idx+1, str, res);
            }
        }
    }
    vector<string> generateParenthesis(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<string> res;
        string str(n*2,' ');
        _genParen(n,n,0,str,res);
        return res;
    }
};

genParen.cc

class Solution {
public:
    void _genParen(int numL, int numR, string & sol, vector<string> & res)
    {
        if(numL == 0 && numR == 0)
            res.push_back(sol);
        else
        {
            // numR should be  > numL
            if(numL == numR)
            {
                sol += "(";
                _genParen(numL-1, numR, sol, res);
            }else if(numL > numR) // more left parentheses left
            {
                return; // error
            }else // more right parentheses
            {
                if(numL > 0)
                {
                    string sol_cpy(sol);
                    sol_cpy += '(';
                    // still add left parentheses
                    _genParen(numL-1, numR, sol_cpy, res);
                }
                sol += ')'; // we can add right parentheses, if there are more right 
                _genParen(numL, numR-1, sol, res);
            }
        }
    }
    
    vector<string> generateParenthesis(int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        // make decisions
        int numL = n, numR = n;
        vector<string> res;
        string sol;
        _genParen(numL, numR, sol, res);
        return res;
    }
};