共计 1184 个字符，预计需要花费 3 分钟才能阅读完成。
题目地址：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);
}
}
