【Generate Parentheses】cpp

题目：

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:

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

代码：

class Solution {
public:
        vector<string> generateParenthesis(int n)
        {
            vector<string> ret;
            vector<char> tmp;
            Solution::dfs(ret, tmp, 0, n, n, n);
            return ret;
        }
        static void dfs( vector<string>& ret, vector<char>& tmp, int sum, int left, int right, int n )
        {
            if ( left==0 && right==0 )
            {
                ret.push_back(string(tmp.begin(),tmp.end()));
                return;
            }
            // '(' or ')'
            if ( left>0 )
            {
                tmp.push_back('(');
                Solution::dfs(ret, tmp, sum+1, left-1, right, n);
                tmp.pop_back();
            }
            if ( right>0 && sum>0 )
            {
                tmp.push_back(')');
                Solution::dfs(ret, tmp, sum-1, left, right-1, n);
                tmp.pop_back();
            }
        }

};

tips：

第一反应是不是stack相关的解法，因为感觉跟逆波兰表达式差不多。

后来发现用‘深搜+剪枝’即可解决。

这里left表示没有使用的'('，right表示没有使用的')'；sum标记使用left和right的情况，使用一次left给sum加1，使用一次right给sum减1。

能迭代下去的核心条件是：使用的sum必须大于等于0.

1. 深搜情况，这里每层有两个分支：'(' 或者 ')'

2. 剪枝条件:

　　a) 只要使用过'('小于n, 则可以加到tmp中

　　b) 使用过的')'小于n, 并且当前的sum是大于0的

=======================================

第二次用dfs过这道题，套路稍微熟悉一些了，考虑dfs的分支顺序：每一层可以加入left括号也可以加入right括号，终止条件的是剩余的left括号数量一定小于right括号的数量。