leetcode22括号生成（String）

发表于 | 分类于

题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

示例

1
2
3
4
5
6
7
8
例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题解

n表示括号的对数，也是左括号和右括号的个数，left表示当前curr中左括号的个数，right表示当前curr中右括号的个数。首先刚开始只能是先有左括号，如果左括号的个数小于n，则可以一直添加左括号到curr;如果右括号的个数小于左括号的个数，则可以继续添加右括号到当前curr；递归的终止条件是right==n，就把curr添加到List。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n==0) return res;
        helper("",res,n,0,0);
        return res;
    }
    public void helper(String curr,List<String> res,int n,int left,int right){
        if(right==n){
            res.add(curr);
            return;
        }
        if(left<n){
            helper(curr+"(",res,n,left+1,right);
        }
        if(right<left){
            helper(curr+")",res,n,left,right+1);
        }
    }
}