题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
输入：n = 1
输出：[“()”]
思路一：更大的n对应的括号怎样由更小的n得到？
题解
因为需要生成所有的可能性，因此这里是一个动态规划。下面问题的关键，即动规思路。
那么，更大的n对应的括号怎样由更小的n得到呢？不能遗漏，也不要重复。我们从易到难地分析：
一个括号：()
两个括号：(()) ()()
三个括号：((())) (()()) (())() ()(()) ()()()
观察到这样一种规律：
f(n) = ‘(’ + f(i) + ‘)’ ∪ f(n - 1 - i) , 0 <= i < n
我们自小到大地枚举i，因此不会出现重复的字符串。分析到这里，可以使用动态规划或者递归的形式实现。动规以空间换时间，效率更高。
Java代码
写于2020年1月：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c)
for (String left: generateParenthesis(c))
for (String right: generateParenthesis(n-1-c))
ans.add("(" + left + ")" + right);
}
return ans;
}
}
Python代码
写于2022年4月：
class Solution(object):
def generateParenthesis(self, n):
if n == 0:
return ['']
rs = []
for i in range(n):
left = self.generateParenthesis(i)
right = self.generateParenthesis(n - i - 1)
for l in left:
for r in right:
rs.append('(' + l + ')' + r)
return rs
思路二：逐字符拓展
题解
换一种思路，我们思考含n对括号的字符串在什么情况下是合规的：
- 必须有n个左括号与n个右括号。
- 自左向右，在任何位置，之前的左括号数目一定要大于右括号数目。
我们基于上面这两点，从前向后，通过逐字符拓展，即一个个加入左括号与右括号的方法，最终生成所有可能性。由于存在多种可能性，也就对应着每次可以新加入一个左括号、也可以新加入一个右括号，这些分支有些最终不能走通（这些不可行的分支对应不符合上述两点条件的情况），所以非常适合用递归实现。
对于递归函数，我们记录当前的字符串是什么、记录当前已经加入了多少个左括号与多少个右括号。对于符合条件的字符串，我们把它加入结果中。
Java代码
写于2020年1月：
import java.util.ArrayList;
import java.util.List;
class Solution {
void dfs(int l,int r,int n,String curr,List<String> list) {
if(l<r) return;
if(l>n||r>n) return;
if(l==n&&r==n) {
list.add(curr);
return;
}
dfs(l+1,r,n,curr+"(",list);
dfs(l,r+1,n,curr+")",list);
}
public List<String> generateParenthesis(int n) {
List<String> list=new ArrayList<String>();
dfs(0,0,n,"",list);
return list;
}
}
Python代码
写于2022年4月：
class Solution(object):
rs = []
def dfs(self, l_num, r_num, n, curr):
if l_num > n or r_num > n or r_num > l_num:
return
if l_num == n and r_num == n:
self.rs.append(curr)
return
self.dfs(l_num + 1, r_num, n, curr + '(')
self.dfs(l_num, r_num + 1, n, curr + ')')
def generateParenthesis(self, n):
self.rs = []
self.dfs(0, 0, n, '')
return self.rs
