括号生成

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode题目，22. Generate Parentheses

先看题目描述

B1xRv6.png

大意就是给定一个数字 n 代表生成括号的对数，让我们返回所有可能的并且有效的括号组合

算法和思路

回溯

  • 当前左右括号都有大于 0 个可以使用的时候，才产生分支；
  • 产生左分支的时候，只看当前是否还有左括号可以使用；
  • 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
  • 在左边和右边剩余的括号数都等于 0 的时候结算

算法源码

dfs(cur + “)”, left, right - 1, res); 前面不需要对 right > 0 进行判断是因为 right 一定大于等于 left，left又一定大于等于 0，而 left 和 right 均为 0 时会结束递归，故 right 一定大于 0，则不需要对 right > 0 进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

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

    private void dfs(String cur, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(cur);
            return;
        }
        if (left > right) {
            return;
        }
        if (left > 0) {
            dfs(cur + "(", left - 1, right, res);
        } 
        dfs(cur + ")", left, right - 1, res);
    }
}

但这个代码其实并不是严格的回溯法的写法，回溯算法重点如下：

「回溯算法」强调了在状态空间特别大的时候，只用一份状态变量去搜索所有可能的状态，在搜索到符合条件的解的时候，通常会做一个拷贝，这就是为什么经常在递归终止条件的时候，有 res.add(new ArrayList<>(path)); 这样的代码。正是因为全程使用一份状态变量，因此它就有「恢复现场」和「撤销选择」的需要

严格按照回溯法实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) return res;
        StringBuilder cur = new StringBuilder();
        dfs(cur, n, n, res);
        return res;
    }

    private void dfs(StringBuilder cur, int left, int right, List<String> res) {
        if (left == 0 && right == 0) {
            res.add(cur.toString());
            return;
        }
        if (left > right) {
            return;
        }
        if (left > 0) {
            cur.append("(");
            dfs(cur, left - 1, right, res);
            cur.deleteCharAt(cur.length() - 1);
        }
        cur.append(")");
        dfs(cur, left, right - 1, res);
        cur.deleteCharAt(cur.length() - 1);
    }
}