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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]题目要求：枚举出所有合理的括号组合。
题目分析：刚开始认为，这个题应该是在二叉树中的某一类遍历，属于深度遍历二叉树得到结果，但是始终没有找到规律。
其实这个题目的输出符合的是“卡特兰数”，即在生成的括号序列中，任何位置，左括号的数目都要大于等于有括号。本着这个原则，看下面代码里的注释就轻松多了。
import java.util.ArrayList; import java.util.List; public class Solution { public List<String> generateParenthesis(int n) { String str=""; List<String> result=new ArrayList<String>(); backtrace(result,str,n,n,n); return result; } /** * @param result 保存所有合理的扩号序列 * @param str 传入的合法序列前缀 * @param left 剩余可添加的左括号数 * @param right 剩余可添加的右括号数 * @param max 总的括号对数 */ public void backtrace(List<String> result,String str,int left,int right,int max){ if(str.length()==2*max){ //如果此时生成的扩号序列已经达到2n个，则递归返回 result.add(str); return; } if(left>0)backtrace(result,str+"(",left-1,right,max); //只要还有剩下左括号，就可以添加进去 if(left<right && right>0)backtrace(result,str+")",left,right-1,max); //如果剩下的右括号，要大于左括号，那么说明已生成的str中，左括号数是较多的，此时便可以加入右括号了 } }