求思路，这个题实在没思路了

一个n＊n的table从左上角走到右下角，（表示往左走，）表示往下走。
最终的path遍历table的一半。

不错，很有意思的题目，学习了

这个题cc150里的2种解法都很好。建议lz去看看。

典型的backtracking问题。leetcode online judge原题，generate parentheses。

1. class Solution {
   
2. public:
   
3.     vector<string> generateParenthesis(int n) {
   
4.         // Start typing your C/C++ solution below
   
5.         // DO NOT write int main() function
   
6.         vector<string> res;
   
7.         generator(res, "", 0, 0, n);
   
8.         return res;
   
9.     }
   
10. 
    
11.     /*
    
12.      * res：结果集
    
13.      * s: 当前已经生成的字符串
    
14.      * l：已经使用的"("的个数
    
15.      * r：已经使用的")"的个数
    
16.      * n："(", ")"最多的个数
    
17.      */
    
18.     void generator(vector<string> &res, string s, int l, int r, int n) {
    
19.         if (l == n) {
    
20.             res.push_back(s.append(n - r, ')'));
    
21.             return;
    
22.         }
    
23. 
    
24.         generator(res, s+"(", l+1, r, n);
    
25.         if (l > r) {
    
26.             generator(res, s+")", l, r+1, n);
    
27.         }
    
28.         return;
    
29.     }
    
30. };
    

复制代码

我觉得可以用递归，如下：

如果我们知道怎么处理n=2 pairs of parentheses，我们就可以通过将the third pair of parentheses插入2 pairs of parentheses的所有valid combination的每一个可能插入的位置来获得3 pairs of parentheses的所有valid的combination

n=2时，valid combination有 ()() 和(())。现在将third pair插入第一个combination，获得
()()(), (())(), ()()(), ()(()), and ()()()

将third pair插入第二个combination，获得
()(()), (()()), ((())), (()()), (())()

以此类推，知道了n-1的解，就可以生成n的解，base case n=1， 只有一种情况：()，用递归获得n>1时的情况。

一个需要注意的问题是，可能生成重复的，可行的解决方法是，建一个hash table，每生成一个combination，check其是否已经在hash table里了，如果不在，插入；否则丢弃。

例如上面的例子，所有unique的combinations有：
()()(), (())(), ()(()), (()()), ((()))

最后输出hash table里所有的combinations即可。

PS: LZ好像漏了一个(()())吧

一个一个“添加括号”，递归
情况只有2种
1）包住原来的
2）在左边或者右边添加
这样可以证明，没有重复计算

递归吧...
看了眼CC比我自己想的简单多了，原来就只知道recursive backtracking
学艺不精啊，自我反思

我觉得这个题可以用……类似二叉树的思路来做？

http://yucoding.blogspot.com/201 ... on-31-generate.html
其实简单的DFS就够用了～