题目：

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
     
       generateParenthesis(int n)        {            vector
      
        ret;            vector
       
         tmp;            Solution::dfs(ret, tmp, 0, n, n, n);            return ret;        }        static void dfs( vector
        
         & ret, vector
         
          & 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括号的数量。