回溯法就是学不会2 —— 括号生成问题

题目描述： 给定括号数量， 判断其能生成的合法括号组合
示例：
括号数量 ： n = 2
输出结果： [(()), ()()]

为什么可以用回溯法：
本题解空间可以用树来表示， 在所有解的基础上去掉不合法结果（即剪枝），因此可以用回溯法解决

以 n = 2 为例， 本题的解空间树如下图所示

得到所有解：

输出结果为： [((((, (((), (()(, (()), ()((, ()(), ())(, ())), )(((, )((), )()(, )()), ))((, ))(), )))(, ))))]

	// n为括号数量， path为临时字符串， result存储结果
    public void dfs(int n, String path, List<String> result){
    	// 字符串长度为2倍的n时，结束
        if(path.length() == 2*n){
            result.add(path);
            return;
        }
		// 加入左括号
        dfs(n, path + "(", result);
        // 加入右括号
        dfs(n, path + ")", result);
    }
1
2
3
4
5
6
7
8
9
10
11
12

剪枝：

方法： 引入开闭括号数量指针，open / close

1. open或close数量大于 n, 剪枝——不合法，开闭括号数量超过最大数量
2. close 数量大于 open , 剪枝 —— 不合法，有闭括号到开括号之前

加入剪枝函数后最终代码：

class Solution {
 public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        dfs(n, "" , list, 0, 0);
        return list;
    }

	// open,close分别表示开闭括号数量指针
    public void dfs(int n, String path, List<String> result, int open, int close){
    	// 剪枝判断语句
        if(open > n || close > open){
            return;
        }
        if(path.length() == 2*n){
            result.add(path);
            return;
        }
        dfs(n, path + "(" ,  result, open+1, close);
        dfs(n, path + ")",  result, open, close+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最后感谢老师提供的思路，谢谢您！！！