algorithms►leetcode

026-括号生成（DFS or DP）

括号生成

方法一：回溯法（DFS）

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
function generateParenthesis(n) {
    const result = [];
    
    function backtrack(current, open, close) {
        // 当字符串长度达到 2n 时，保存结果
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        // 只要左括号数量小于 n，就可以添加左括号
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        
        // 只有右括号数量小于左括号时，才能添加右括号（保证有效性）
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }
    
    backtrack('', 0, 0);
    return result;
}

// 示例测试
console.log(generateParenthesis(3)); 
// 输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
代码解析
  1. backtrack 函数：
    • current：当前构建的字符串。
    • open：已使用的左括号数量。
    • close：已使用的右括号数量。
  2. 终止条件：当 current.length === 2 * n 时，说明已生成一个有效组合，存入 result。
  3. 递归添加括号：
    • 如果左括号数量 < n，可以继续加 (。
    • 如果右括号数量 < 左括号数量，可以加 )（确保有效性）。

方法二：动态规划（DP）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function generateParenthesis(n) {
    const dp = Array.from({ length: n + 1 }, () => []);
    dp[0] = [""]; // 初始化：0 对括号是空字符串
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            // 组合所有可能的子问题解
            for (const left of dp[j]) {
                for (const right of dp[i - j - 1]) {
                    dp[i].push(`(${left})${right}`);
                }
            }
        }
    }
    
    return dp[n];
}

// 示例测试
console.log(generateParenthesis(3)); 
// 输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
代码解析
  1. dp 数组：
    • dp[i] 存储 i 对括号的所有有效组合。
    • 初始化 dp[0] = [""]（0 对括号是空字符串）。
  2. **递推填充 dp**：
    • 对于 i 对括号，遍历 j 从 0 到 i-1：
      • dp[j] 的所有组合作为内部括号 left。
      • dp[i-j-1] 的所有组合作为外部括号 right。
      • 组合成 (${left})${right} 并存入 dp[i]。

两种方法对比

方法 时间复杂度 空间复杂度 适用场景
回溯法 O(4ⁿ/√n) O(n)（递归栈） 代码简洁，通用
动态规划 O(4ⁿ/√n) O(4ⁿ/√n) 可复用子问题解

如何选择？

  • 面试/快速实现：用 回溯法（逻辑清晰，代码短）。
  • 多次调用/优化：用 动态规划（避免重复计算）。

示例图解（n=2）

回溯法流程

1. 开始 -> '(' 
   -> '((' 
      -> '(()' 
         -> '(())' ✅
   -> '()'
      -> '()('
         -> '()()' ✅
结果：["(())", "()()"]

动态规划流程

dp[0]: [""]
dp[1]: ["()"]
dp[2]:
  - j=0: "(" + dp[0] + ")" + dp[1] → "()()"
  - j=1: "(" + dp[1] + ")" + dp[0] → "(())"
结果：["(())", "()()"]

总结

  • 回溯法：通过递归 + 剪枝生成所有有效组合。
  • 动态规划：利用子问题的解构建当前解（类似数学归纳法）。
  • JavaScript 注意点：递归时用 current + '(' 而非 +=（避免修改原字符串）。