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对括号，就有n个左括号和n个右括号，我们定义两个变量left和right分别表示字符串中左括号的个数和右括号的个数。如果字符串中右括号的个数大于左括号的个数，这就会出现)(的情况，所以不作处理，直接返回。当左括号的个数小于n时，这个时候就可以添加左括号，右括号个数小于左括号时，可以添加右括号。也就是说，两种情况都可以，所以都进行尝试。当字符串长度和n*2相等时就可以添加到List中了。
class Solution {
public List<String> generateParenthesis(int n) {
/*
*/
List<String> list=new ArrayList<>();
helper(list,"",0,0,n);
return list;
}
/*
求n时的括号组合。
left表示此时字符串中左括号的个数，right表示字符串中右括号的个数，
*/
public void helper(List<String> list,String str,int left,int right,int n){
if(str.length()==n*2){
list.add(str);
return ;
}
//当left小于n时，表示还可以添加左括号，当left大于right时，表示可以添加右括号
//注意：该字符串中，左括号的个数不可能小于右括号的个数，因为这样就是无效的输出。
if(left<n)
helper(list,str+"(",left+1,right,n);
if(left>right)
helper(list,str+")",left,right+1,n);
}
}