回溯算法：括号生成

22. 括号生成

本篇文章来分析「括号匹配」问题。对于「括号」相关的问题，有两种题型：判断合法性 && 括号生成

判断合法性，详情可见题目有效的括号，这一类题目基本上是利用栈来辅助判断

而对于「括号生成」问题，就需要用到回溯算法，下面就来详细分析该问题。详情可见题目括号生成

这里给出两种思路，一种是本人借鉴「全排列」的思路 (详情可见排列/组合/子集问题)，另外一种是更加优化的思路

本人思路 (极其拉胯 😭)

虽然这种思路略微的拉胯，但还是要好好纪念一下滴，谁叫是自己写出来的呢！无兴趣的可以直接看下面的思路

先给出这种思路的回溯树，如下：

如果需要达到去重的效果，那么括号就必须有序，这个在介绍「全排列」的时候详细分析过

即然明确了思路，那么代码也就可以很好的写出！！(我们先不考虑括号的合法性，仅仅把所有非重复的排列列举出来)


x
// 记录使用情况
private boolean[] used;
// 记录当前括号组合
private StringBuffer sb;
// 记录所有符合条件的结果
private List<String> res;

public List<String> generateParenthesis(int n) {
    sb = new StringBuffer();
    res = new ArrayList<>();
    used = new boolean[n * 2];
    Arrays.fill(used, false);
    // 存储所有括号 (按序)
    char[] parentheses = new char[n * 2];
    for (int i = 0; i < n; i++) {
        parentheses[i] = '(';
    }
    for (int i = n; i < n * 2; i++) {
        parentheses[i] = ')';
    }
    backtrack(parentheses);
    return res;
}
private void backtrack(char[] parentheses) {
    // 说明括号的数量已经满足条件
    if (sb.length() == parentheses.length) {
        res.add(sb.toString());
        return ;
    }
    for (int i = 0; i < parentheses.length; i++) {
        if (used[i]) {
            continue;
        }
        // 去重 (原因可见全排列，有详细分析)
        if (i > 0 && parentheses[i] == parentheses[i - 1] && !used[i - 1]) {
            continue;
        }
        sb.append(parentheses[i]);
        used[i] = true;
        backtrack(parentheses);
        used[i] = false;
        sb.deleteCharAt(sb.length() - 1);
    }
}

上述代码把所有非重复的结果全部遍历出来了，但此时我们还没有验证括号的合法性

根据惯性思维，一开始就想着在递归回溯的过程中同时维护一个栈，来验证当前结果的合法性！

核心代码如下：


xxxxxxxxxx
// 先序阶段
// 如果当前字符是 '('，入栈
if (parentheses[i] == '(') {
    stack.push(parentheses[i]);
  // 如果当前字符是 ')'
} else {
    // 如果此时栈为空，那么非法，跳过
    if (stack.isEmpty()) continue ;
    // 不为空时，弹出最上方的 '('
    stack.pop();
}

// 中间代码逻辑不变 ......

// 后序阶段
// 如果当前字符是 ')'，说明在先序阶段我们弹出了最上方的 '('，所以此时需要恢复最上方的 '('
if (parentheses[i] == ')') {
    stack.push('(');
  // 如果当前字符是 '('，说明在先序阶段我们把 '(' 压入栈了，所以此时需要弹出最上方的 '('
} else {
    stack.pop();
}

有没有发现在这两个阶段的操作具有高度的对称性！！

分析时间复杂度

$O((2n)!)$

而且我们的回溯树还存在很多冗余，如下图所示：

从图中可以明显的看到绿色和橙色部分均和自己左边的部分有重复

优化思路 (喜出望外 😊)

首先，我们的选择不再是2n个选择，这样会存在大量的冗余。假设n = 3，第一步我们在((()))六个中选择其实和在()两个中选择无差别，前者只会造成更多的冗余

所以我们现在优化的思路就是每次都在()2n $O(2^{2n})$ (仅为估算)

其次，我们还优化了一下判断合法性的策略。对于一个字符串s来说，s的任意一个子串[0...i]中，(的数量肯定大于或等于)的数量

根据上面的分析，我们可以给出代码：


xxxxxxxxxx
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
    backtrack(n, n, new StringBuffer());
    return res;
}
// left : 还可用的左括号的数量
// right : 还可用的右括号的数量
private void backtrack(int left, int right, StringBuffer track) {
    // 注意 left right 是还剩的数量
    if (left > right) return ;
    if (left < 0 || right < 0) return ;
    // 满足条件：左右括号刚好用完
    if (left == 0 && right == 0) {
        res.add(track.toString());
        return ;
    }
    
    // 选择 (
    track.append('(');
    backtrack(left - 1, right, track);
    track.deleteCharAt(track.length() - 1);
    
    // 选择 )
    track.append(')');
    backtrack(left, right - 1, track);
    track.deleteCharAt(track.length() - 1);
}