vvrf / DSA.log

问题拆解

生成所有由 n 对括号组成的合法序列。暴力做法是枚举 2n 个位置上每个位置放 ( 还是 ) 的全部 2^{2n} 种组合，再逐个验证合法性——绝大多数组合在前几个字符就已经废了，比如以 ) 开头的全军覆没，验证纯属浪费。

合法括号序列有个逐前缀的刻画：任何前缀里右括号数都不能超过左括号数，且最终两者都等于 n。这个条件是每一步局部可检查的，这正是回溯最喜欢的结构——不用等串拼完才验证，摆每个字符时就能判断这条路还有没有救。

维护两个计数 open 和 close：open < n 时可以放左括号（还有存货）；close < open 时可以放右括号（有未配对的左括号等着它）。守住这两条，走到长度 2n 的每条路径都自动合法。

open/close 计数回溯

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, new StringBuilder(), 0, 0, n);
    return result;
}

private void backtrack(List<String> result, StringBuilder path, int open, int close, int n) {
    if (path.length() == 2 * n) {
        result.add(path.toString()); // 剪枝保证到这里必然合法
        return;
    }
    if (open < n) { // 左括号还有存货
        path.append('(');
        backtrack(result, path, open + 1, close, n);
        path.deleteCharAt(path.length() - 1); // 撤销选择
    }
    if (close < open) { // 有未配对的左括号
        path.append(')');
        backtrack(result, path, open, close + 1, n);
        path.deleteCharAt(path.length() - 1);
    }
}

def generateParenthesis(n: int) -> list[str]:
    result = []
    path = []

    def backtrack(open_count: int, close_count: int) -> None:
        if len(path) == 2 * n:
            result.append("".join(path))  # 剪枝保证到这里必然合法
            return
        if open_count < n:  # 左括号还有存货
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()  # 撤销选择
        if close_count < open_count:  # 有未配对的左括号
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()

    backtrack(0, 0)
    return result

func generateParenthesis(n int) []string {
    result := []string{}
    path := make([]byte, 0, 2*n)
    var backtrack func(open, close int)
    backtrack = func(open, close int) {
        if len(path) == 2*n {
            result = append(result, string(path)) // 剪枝保证到这里必然合法
            return
        }
        if open < n { // 左括号还有存货
            path = append(path, '(')
            backtrack(open+1, close)
            path = path[:len(path)-1] // 撤销选择
        }
        if close < open { // 有未配对的左括号
            path = append(path, ')')
            backtrack(open, close+1)
            path = path[:len(path)-1]
        }
    }
    backtrack(0, 0)
    return result
}

pub fn generate_parenthesis(n: i32) -> Vec<String> {
    fn backtrack(result: &mut Vec<String>, path: &mut String, open: i32, close: i32, n: i32) {
        if path.len() as i32 == 2 * n {
            result.push(path.clone()); // 剪枝保证到这里必然合法
            return;
        }
        if open < n { // 左括号还有存货
            path.push('(');
            backtrack(result, path, open + 1, close, n);
            path.pop(); // 撤销选择
        }
        if close < open { // 有未配对的左括号
            path.push(')');
            backtrack(result, path, open, close + 1, n);
            path.pop();
        }
    }
    let mut result = Vec::new();
    backtrack(&mut result, &mut String::new(), 0, 0, n);
    result
}

两个条件里更容易写错的是第二个：close < open 而不是 close < n。后者只保证右括号总数不超标，挡不住 )( 这种前缀非法的序列——右括号能不能放，取决于此刻有没有落单的左括号，而不是配额还剩多少。第一个条件写成 open < n 则天然保证左括号不超发，两条合在一起，到达 2n 长度时必有 open == close == n，终点无需再验证。

递归返回后要撤销刚才的追加（pop / 删末字符），让 path 回到进入前的状态，兄弟分支才能在干净的前缀上继续——“做选择、递归、撤销”这三拍是回溯的节奏本身。解的个数是卡特兰数 C(n) = C(2n, n) / (n + 1)，剪枝后搜索树的节点数与解数同阶，没有一步走进死路。

复杂度

指标	复杂度	原因
时间	`O(4^n / √n)`	第 n 个卡特兰数的量级，每个解拷贝 O(n)
空间	`O(n)`	递归深度与 path 长度都是 2n（输出不计）

可以迁移的模式

生成类问题优先找“逐前缀可判定”的合法条件，边构造边剪枝，而不是生成后过滤；
用少量计数器（这里是 open/close）概括前缀状态，比携带整个字符串判断更省；
回溯三拍：追加、递归、撤销，共享的 path 一定要在返回后复原。

凡是解空间是“一步步做选择”长出来的树，并且坏选择能提前识别，这套计数回溯就能直接搬过去。