0022.括号生成

难度：🟡 中等

标签：字符串、动态规划、回溯

链接：22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

解题思路

核心思想

本题的目标是生成所有合法的括号组合。一个“有效”的括号组合需要满足两个条件：

1. 左右括号的数量相等，都等于 n。

2. 在任何一个位置，其左边的左括号数量总是大于或等于右括号的数量。

这个问题涉及到所有可能组合的生成，是 回溯法 的经典应用场景。

思路选择

回溯法 + 剪枝 是解决此问题的标准最优思路。我们不再像暴力法那样生成所有 2^(2n) 种可能，而是在递归生成过程中，只构建那些可能有效的组合。

• 我们可以定义一个递归函数，它在构建字符串的过程中，实时跟踪已使用的左括号和右括号的数量。

• 通过添加约束条件（剪枝），我们确保在任何时候都不会构建出无效的前缀。

关键步骤

1. 定义回溯函数：创建一个递归函数，例如 backtrack(path, openCount, closeCount)。

   • path: 当前正在构建的括号序列。

   • openCount: 已使用的左括号数量。

   • closeCount: 已使用的右括号数量。

2. 设置终止条件 (Base Case)：当 path 的长度达到 2 * n 时，说明我们已经构建了一个完整的组合，将其加入结果集，并结束当前递归。

3. 递归与剪枝： a. 添加左括号: 如果已使用的左括号数量 openCount 小于 n，我们就可以添加一个左括号 (。然后带着更新后的状态继续递归。 b. 添加右括号: 如果已使用的右括号数量 closeCount 小于已使用的左括号数量 openCount，我们就可以添加一个右括号 )。这个条件是核心剪枝，它保证了生成的序列始终是有效的。 c. 撤销选择: 每次递归调用返回后，都需要将 path 恢复到之前的状态（即 path.pop()），以便探索其他可能性。

代码实现 (推荐)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const results = [];
    const path = [];

    const backtrack = (openCount, closeCount) => {
        // 当括号序列长度达到 2n，说明找到一个完整解
        if (path.length === n * 2) {
            results.push(path.join(''));
            return;
        }

        // 剪枝1：如果左括号数量小于 n，可以添加左括号
        if (openCount < n) {
            path.push('(');
            backtrack(openCount + 1, closeCount);
            path.pop(); // 撤销选择
        }

        // 剪枝2：如果右括号数量小于左括号数量，可以添加右括号
        if (closeCount < openCount) {
            path.push(')');
            backtrack(openCount, closeCount + 1);
            path.pop(); // 撤销选择
        }
    };

    backtrack(0, 0);
    return results;
};

原始代码分析 (用户提供)

您提供的解法是一种“先生成，后验证”的暴力回溯法，虽然能得到正确答案，但效率较低。

// 验证函数：检查括号序列是否有效
var isValid = function (result) {
    let count = 0;
    for (let i = 0; i < result.length; i++) {
        if (result[i] === '(') count++;
        else if (count >= 1) count--;
        else return false; // 右括号多于左括号，无效
    }

    return count === 0; // 最终左右括号数量需相等
}

// 回溯函数：生成所有可能的组合
var backTracking = function (path, results, count) {
    // 长度达到要求后，进行验证
    if (path.length >= count) {
        if (isValid(path)) results.push(path.join(''));
        return;
    }
    // 无差别地添加 '(' 或 ')'
    let choices = ['(', ')'];
    for (let i = 0; i < choices.length; i++) {
        path.push(choices[i]);
        backTracking(path, results, count);
        path.pop();
    }
}
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const results = [];
    backTracking([], results, n * 2);
    return results;
};

• 优点：思路清晰地将“生成”和“验证”两个过程分离开来。

• 待改进：效率极低。该算法会生成所有 2^(2n) 种可能的 ( 和 ) 组合，然后对每一种都进行一次 O(n) 的验证。推荐解法通过在生成过程中进行“剪枝”，从根本上避免了大量无效组合的产生，大大提高了算法效率。

复杂度分析

• 时间复杂度：O(4ⁿ / √n) 这是一个组合问题，解的数量与卡特兰数相关。这是一个比较宽松的上限，但可以说明其复杂度是指数级的。

• 空间复杂度：O(n) 不考虑存储结果的数组，空间复杂度主要由递归的深度决定，最深为 2n。

相关题目

• 0017.电话号码的字母组合

• 0046.全排列

• 0093.复原IP地址

总结

本题是回溯算法的经典案例。通过在递归过程中加入明确的约束条件（剪枝），可以有效地减少搜索空间，避免无效的计算。理解如何将问题的“有效性”规则转化为回溯的“剪枝”条件，是掌握此算法的关键。