[解题思路]
典型的递归。一步步构造字符串。当左括号出现次数<n时，就可以放置新的左括号。当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。
public class Solution { public ArrayList<String> generateParenthesis(int n) { ArrayList<String> result = new ArrayList<String>(); StringBuilder builder = new StringBuilder(); generate(result, builder, n, n); return result; } public void generate(ArrayList<String> result, StringBuilder builder, int start, int end){ if(start == 0 && end == 0){ result.add(builder.toString()); return; } if(start > 0){ builder.append(‘(‘); generate(result, builder, start-1, end); builder.deleteCharAt(builder.length()-1); } if(start < end){ builder.append(‘)‘); generate(result, builder, start, end -1); builder.deleteCharAt(builder.length()-1); } } }
注意：
builder.deleteCharAt(builder.length()-1);
eg : n=2 时 builder 先是 “(( ))” ,添加到 result ArrayList中去
然后 delete 成为 “(”, 此时 end > start, 然后 builder 成为 “()” 在成为 “（）（）”