[LeetCode]22.GenerateParentheses

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

For example, given n &＃61; 3, a solution set is:

["((()))","(()())","(())()","()(())","()()()"
]


用二叉树形象的表示这种关系。然后再把二叉树转化为代码的形式。因为二叉树的定义就是递归定义的&＃xff0c;因此本题很明显应该使用递归的形式。

就如同遍历查找一棵二叉树一样&＃xff0c;只不过这个是一个个往上加。

public List<String> generateParenthesis(int n) {List<String> res &＃61; new ArrayList<String>();if (n &＃61;&＃61; 0)return res;dfs(res, "", n, n);return res;}private void dfs(List<String> res, String tem, int left, int right) {if (0 &＃61;&＃61; left && 0 &＃61;&＃61; right) {res.add(tem);return;} else if (left > 0)dfs(res, tem &＃43; &＃39;(&＃39;, left - 1, right);if (left <right)dfs(res, tem &＃43; &＃39;)&＃39;, left, right - 1);}

这种递归到最后自然就都加上去了。