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:

"((()))", "(()())", "(())()", "()(())", "()()()"

tag: backtracking

7/10/2015 udpate

DFS approach, add some restrictions to guarantee the validation of parentheses

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string thisAns;
        dfs(n, 0, 0, thisAns, ans);
        return ans;
    }
    void dfs(int total, int left, int right, string& thisAns, vector<string>& ans){
        //total - total numbers of parentheses
        //left - number of left parentheses
        //right - number of right parenthese
        if(left + right == 2 * total){
            ans.push_back(thisAns);
            return ;
        }
        if(left == total){
            //push right parenthese
            thisAns.push_back(')');
            dfs(total, left, right + 1, thisAns, ans);
            thisAns.pop_back();
        }else if(left > right){
            //left < total
            //left >= total
            //push either left or right
            thisAns.push_back('(');
            dfs(total, left + 1, right, thisAns, ans);
            thisAns.pop_back();
            
            thisAns.push_back(')');
            dfs(total, left, right + 1, thisAns, ans);
            thisAns.pop_back();
        }
        else{
            //left < total
            //left == right
            //push left
            thisAns.push_back('(');
            dfs(total, left + 1, right, thisAns, ans);
            thisAns.pop_back();
        }
    }
};

一开始想用递归了，递归到n=1的情况，然后一层一层把结果修饰到n的情况。但这样很难去重。

比如n=2时，先考虑n=1的情况：

“()”

n=2时，向里面插入一对”()”，则有六种情况：

“()()”, “(())”，”(())“, “(())”，”(())“，”()()”

可以考虑在最后取解集的前一半，以为解集是对称的，后一半与前一半相同。

于是改思路，并backtracking的思路来做。

_generateParenthesis(int numOfLeftPar, int numOfRightPar, string thisRe)

numOfLeftPar为当前状态下还剩余的可用的左括号”(“数量；

numOfRightPar为当前状态下还剩余的可用的右括号”)”数量；

thisRe为当前状态下的尝试字符串；

当numOfLeftPar 和 numOfRightPar均为0时，匹配成功，将thisRe存入解集re中。

当numOfLeftPar小于numOfRightPar时，匹配不合法，且下面的匹配不可能有合法解，进行剪枝。

代码：

class Solution {
public:
    vector<string> re;
    vector<string> generateParenthesis(int n) {
        string tmp;
        _generateParenthesis(n, n, tmp);
        return re;
    }
    void _generateParenthesis(int numOfLeftPar, int numOfRightPar, string thisRe){
        if(numOfLeftPar == 0 && numOfRightPar == 0){//found one
            re.push_back(thisRe);
        }
        else if(numOfLeftPar > numOfRightPar){// no valid result
            return;
        }
        else{
            if(numOfLeftPar > 0){ //insert a left parenthese
                numOfLeftPar--;
                thisRe.push_back('(');
                _generateParenthesis(numOfLeftPar, numOfRightPar, thisRe);
                thisRe.pop_back();
                numOfLeftPar++;
            }
            if(numOfRightPar > 0){ // insert a right parenthese
                numOfRightPar--;
                thisRe.push_back(')');
                _generateParenthesis(numOfLeftPar, numOfRightPar, thisRe);
                thisRe.pop_back();
                numOfRightPar++;
            }
        }
    }
};