题目地址：
https://leetcode-cn.com/probl...
题目描述：
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
这一题可以用递归来做，若现在有n-1对的有效括号组合，求第n对的有序括号组合，只需要在n-1对的组成中不断添加"()"就可以保证生成有效的括号组合，不过这样可能会重复，因此再使用一个hash表来去重。
java ac代码:
class Solution {
HashSet<String> set = new HashSet(2000);
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if(n == 1)
{
ans.add("()");
set.add("()");
return ans;
}
List<String>temp = generateParenthesis(n-1);
for(String s:temp)
{
int k = 0;
while(k < s.length()){
if(!set.contains(s.substring(0,k+1)+"()"+s.substring(k+1))){
ans.add(s.substring(0,k+1)+"()"+s.substring(k+1));
set.add(s.substring(0,k+1)+"()"+s.substring(k+1));
}
k++;
}
}
return ans;
}
}不过这一题标准的解法是回溯法。回溯法在生成全集的过程中进行剪枝，使得效率最大。并且不需要判重，因为回溯就是一次性生成全集，所以不会重复。剪枝需要用到两个变量，一个是当前过程中左括号数量l和当前过程中右括号数量r，若r>l则一定无解，则剪去这个部分。
java ac代码：
class Solution {
List<String> ans = new ArrayList();
public List<String> generateParenthesis(int n) {
char[]temp = new char[n*2];
temp[0] = '(';
backtrack(1,n*2,1,0,temp);
return ans;
}
void backtrack(int i,int n,int l,int r,char[]temp)
{
if(i == n)
{
if(l == r)
ans.add(new String(temp));
return;
}
if(r>l)return;
temp[i] = '(';
backtrack(i+1,n,l+1,r,temp);
temp[i] = ')';
backtrack(i+1,n,l,r+1,temp);
}
}