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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
解题思路： 这道题大概用递归就可以弄出来了吧。
设置一个num，当string中加上一个 '(' 的时候，就num++，当string中加上一个 ')' 的时候，就num--，所以需要判断num的大小。当num == 0的时候，只能添加 '(' ，当num == 2*n - str.length() 的时候，只能添加 ')' ，当num在 0 < num < 2*n - str.length() 的时候，就两者都可以添加。这样不断递归就能得到结果。
[java] view plain copy print ? public class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<String>(); if(n == 0) return result; getstring(0,0,"",2*n,result); return result; } public void getstring(int x,int num,String str,int n,List<String> result) { if(x == n-1) result.add(str+')'); else { if(num > 0) getstring(x+1,num-1,str+')',n,result); if(num < n-x) getstring(x+1,num+1,str+'(',n,result); } } } public class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<String>(); if(n == 0) return result; getstring(0,0,"",2*n,result); return result; } public void getstring(int x,int num,String str,int n,List<String> result) { if(x == n-1) result.add(str+')'); else { if(num > 0) getstring(x+1,num-1,str+')',n,result); if(num < n-x) getstring(x+1,num+1,str+'(',n,result); } } }
