[LeetCode][Java] Generate Parentheses

题目:

Givennpairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

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

题意：

给定n对括号，生成这些括号的所有正确组合。

比如，当n=3时，正确的解决方案为：

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

算法分析：

* 用dfs思想做递归就好了，记好了先写base case，left，right走过一遍了，，可以把这个String加进list* 注意，左括号的数不能大于右括号，要不然那就意味着先尝试了右括号而没有左括号，类似“)(” 这种解是不合法的。* 深度优先遍历思想:先遍历左子树，直到遍历到末尾节点，再回溯到开始的根节点，遍历右子树，直到遍历完毕。

AC代码：

public class Solution {public List<String> generateParenthesis(int n){if(n<=0) return null;ArrayList<String> list = new ArrayList<String>();String str = new String();dfs(list,str,n,n);return list;}private void dfs(ArrayList<String> list, String str, int left, int right){if(left>right) return;//problem with ")("if(left==0&&right==0)list.add(str);//left right都为零是直接跳出所有递归if(left>0) dfs(list,str+"(",left-1,right);if(right>0) dfs(list, str+")",left,right-1);}}

只要有信心，人永远不会挫败