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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]这道题的意思是给定一个数字n，让生成共有n个括号的所有正确的形式。
首先我们想到递归Recursion的方法。我们定义两个变量left和right分别表示剩余左右括号的个数，如果在某次递归时，左括号的个数大于右括号的个数，说明此时生成的字符串中右括号的个数大于左括号的个数，即会出现’)(‘这样的非法串，所以这种情况直接返回，不继续处理。如果left和right都为0，则说明此时生成的字符串已有3个左括号和3个右括号，且字符串合法，则存入结果中后返回。如果以上两种情况都不满足，若此时left大于0，则调用递归函数，注意参数的更新，若right大于0，则调用递归函数，同样要更新参数。代码如
public class Solution { public List<String> generateParenthesis(int n) { ArrayList<String> res = new ArrayList<String>(); dfs(res, n, n, ""); return res; } public void dfs(ArrayList<String> res,int left,int right, String str){ if(left < 0 || right < 0 || left > right){ return; } if(left == 0 && right == 0){ res.add(str); return ; } if(left > 0){ dfs(res, left - 1, right, str + '('); } if(right > 0){ dfs(res, left, right - 1, str + ')'); } } }第二种结果通过观察规律 n＝1: ()
n=2: (()) ()()
n=3: (()()) ((())) ()(()) (())() ()()() 找左括号，每找到一个左括号，就在其后面加一个完整的括号，最后再在开头加一个()，就形成了所有的情况，需要注意的是，有时候会出现重复的情况，所以我们用set数据结构，好处是如果遇到重复项，不会加入到结果中，最后我们再把set转为ArrayList即可，参见代码如下：
public class Solution{ public List<String> generateParenthesis(int n){ Set<String> set = new HashSet<String>(); if(n == 0){ set.add(""); }else{ List<String> prev = generateParenthesis(n - 1); for(String str : prev){ for(int i = 0; i < str.length(); i++){ if(str.charAt(i) == '('){ String s = insertInside(str, i); set.add(s); } } if(!set.contains("()" + str)){ set.add("()" + str); } } } return new ArrayList(set); } public String insertInside(String str, int leftindex){ String left = str.substring(0, leftindex + 1); String right = str.substring(leftindex + 1, str.length()); return left + "()" + right; } }