❌

阅读视图

发现新文章，点击刷新页面。

回溯算法：选→钻→退→删，掌握穷举的艺术

✇掘金 前端
颜酱

回溯算法：选→钻→退→删，掌握穷举的艺术

回溯算法是算法领域的核心思想之一，尤其在处理「穷举所有可能解」的问题时堪称"神器"。本文将从核心思路出发，通过"选一个数→钻到底→退回来→删掉这个数→选下一个数→再钻到底"这个固定节奏，带你彻底掌握回溯算法。

一、回溯核心原理：选→钻→退→删的固定节奏

一句话记牢回溯的执行过程

选一个数→钻到底→退回来→删掉这个数→选下一个数→再钻到底，直到所有数都试完，最后收集所有符合条件的路径。

选了就往下钻，走不通就退回来擦脚印，换条路再试。很多人一开始都会被递归的多层调用绕晕，但只要抓住 push（选数）→ 递归（钻深层）→ pop（擦脚印） 这个固定节奏，再结合剪枝提前止损，所有回溯题都能套模板解决～

核心四要素

任何回溯问题都能拆解为以下4个核心部分：

要素 作用 示例（组合总和）
路径 已经做出的选择（比如选了哪些数） path = [2,3]（表示选了2和3）
选择列表 当前步骤可选择的选项（比如还能选哪些数） nums = [2,3,6,7]，已选2则可选3/6/7
终止条件 什么时候停止探索（找到解/走到底） 路径和等于目标值，或路径和超过目标值
剪枝 提前排除无效路径（核心优化） 路径和超过目标值，直接停止当前路径

关键理解

  • 递归是"往下钻"：每选一个数，就递归调用backtrack，相当于"往下走一步"
  • return 是"往回退"：触发终止条件（找到解/和超了），就结束当前递归，回到上一层
  • pop 是"擦脚印"：回到上一层后，必须执行path.pop()，把刚才选的数删掉，才能"换另一个数选"
  • for 循环是"选岔路"：每一层的 for 循环，就是在当前位置选不同的数（岔路），试完一条再试下一条

通用模板

// 回溯核心函数
function backtrack(路径, 选择列表, 其他参数) {
  // 1. 终止条件：找到解，记录结果并返回
  if (满足终止条件) {
    结果列表.push(路径的拷贝); // 注意：要拷贝，否则会被后续修改
    return;
  }

  // 2. 遍历所有可选选项
  for (const 选项 of 选择列表) {
    // 剪枝：提前排除无效选项（关键优化）
    if (选项无效) continue;

    // 3. 做选择：把当前选项加入路径（选数）
    路径.push(选项);

    // 4. 递归探索：基于当前选择，继续往下走（钻到底）
    backtrack(路径, 新的选择列表, 其他参数);

    // 5. 撤销选择（回溯核心）：回到上一步，换选项（退回来→删掉这个数）
    路径.pop();
  }
}

// 主函数
function solveProblem(参数) {
  const 结果列表 = []; // 存储所有符合条件的解
  backtrack([], 初始选择列表, 初始参数); // 初始路径为空
  return 结果列表;
}

二、入门示例：组合总和（可视化理解）

为了让你快速理解回溯的核心节奏，我们先从组合总和这个经典入门题入手，通过可视化打印完整展示「选→探→撤」的全过程。

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合（数字可以无限制重复被选取）。

  • 示例：输入 candidates = [2,3,7]，target = 7，输出 [[2,2,3],[7]]。

完整代码实现

/**
 * 组合总和：找所有和为目标值的组合（可视化打印版）
 * @param {number[]} candidates - 候选数组
 * @param {number} target - 目标和
 * @returns {number[][]} - 所有符合条件的组合
 */
function combinationSum(candidates, target) {
  const result = []; // 存储最终结果
  candidates.sort((a, b) => a - b); // 排序便于剪枝
  let recursionLevel = 0; // 标记递归层级，用于可视化缩进

  // 回溯函数：path=当前路径，sum=当前路径和，start=起始索引（避免重复组合）
  function backtrack(path, sum, start) {
    // 层级+1，生成缩进（每级2个空格）
    recursionLevel++;
    const indent = '  '.repeat(recursionLevel - 1);
    const levelTag = `【层级${recursionLevel}】`;

    // 🟢 调用阶段：打印当前层级初始状态
    console.log(
      `${indent}🟢 ${levelTag} 调用阶段 → path=${JSON.stringify(path)}, sum=${sum}, start=${start}`
    );

    // 终止条件1：路径和等于目标值，记录结果
    if (sum === target) {
      result.push([...path]); // 拷贝路径，避免后续修改
      console.log(
        `${indent}✅ ${levelTag} 找到有效组合 → ${JSON.stringify(path)}，result=${JSON.stringify(result)}`
      );
      // 层级-1，准备返回
      recursionLevel--;
      console.log(`${indent}🔴 ${levelTag} 返回阶段 → 找到解，回到上一层`);
      return;
    }
    // 终止条件2：路径和超过目标值，直接返回（剪枝）
    if (sum > target) {
      console.log(`${indent}🚫 ${levelTag} 剪枝 → sum=${sum} > target=${target}，直接返回`);
      recursionLevel--;
      console.log(`${indent}🔴 ${levelTag} 返回阶段 → 剪枝返回，回到上一层`);
      return;
    }

    // 遍历选择列表（从start开始，避免重复组合）
    for (let i = start; i < candidates.length; i++) {
      const num = candidates[i];
      console.log(`${indent}🔍 ${levelTag} 遍历i=${i} → 尝试选数字${num}，当前sum=${sum}`);

      // 排序剪枝：当前数+已选和>目标值，后续数更大，无需继续
      if (sum + num > target) {
        console.log(
          `${indent}🚫 ${levelTag} 排序剪枝 → ${sum}+${num}=${sum + num} > ${target}，break循环`
        );
        break;
      }

      // 做选择：加入当前数（选数）
      path.push(num);
      console.log(
        `${indent}✅ ${levelTag} 选数字${num} → path=${JSON.stringify(path)}, sum=${sum + num}`
      );

      // 🟡 暂停阶段：调用下一层，当前层级暂停
      console.log(`${indent}🟡 ${levelTag} 暂停阶段 → 调用下一层backtrack，等待返回`);
      // 递归探索：数字可重复选，所以start仍为i（钻到底）
      backtrack(path, sum + num, i);
      console.log(`${indent}🔴 ${levelTag} 返回阶段 → 从下一层返回，继续执行`);

      // 撤销选择：回溯核心（退回来→删掉这个数）
      path.pop();
      console.log(
        `${indent}🔵 ${levelTag} 撤销阶段 → 撤销数字${num} → path=${JSON.stringify(path)}, sum=${sum}`
      );
    }

    // 层级-1，准备返回
    recursionLevel--;
    console.log(`${indent}🔴 ${levelTag} 返回阶段 → for循环结束，回到上一层`);
  }

  // 初始调用：空路径、和为0、从索引0开始
  console.log('========== 开始执行组合总和 ==========');
  backtrack([], 0, 0);
  console.log('========== 执行结束 ==========');
  return result;
}

// 测试：输入 [2,3,7], 7 → 输出 [[2,2,3],[7]]
console.log('最终结果：', combinationSum([2, 3, 7], 7));

各个图标的含义：

  • 🟢 调用阶段：进入递归时的状态
  • 🔍 遍历阶段：尝试选择数字
  • ✅ 选择阶段：成功选择数字
  • 🟡 暂停阶段：调用下一层递归
  • 🔴 返回阶段：从下一层返回
  • 🔵 撤销阶段：删除数字（擦脚印）
  • 🚫 剪枝阶段：提前终止无效路径

控制台输出示例：

========== 开始执行组合总和 ==========
🟢 【层级1】 调用阶段 → path=[], sum=0, start=0
🔍 【层级1】 遍历i=0 → 尝试选数字2，当前sum=0
✅ 【层级1】 选数字2 → path=[2], sum=2
🟡 【层级1】 暂停阶段 → 调用下一层backtrack，等待返回
  🟢 【层级2】 调用阶段 → path=[2], sum=2, start=0
  🔍 【层级2】 遍历i=0 → 尝试选数字2，当前sum=2
  ✅ 【层级2】 选数字2 → path=[2,2], sum=4
  🟡 【层级2】 暂停阶段 → 调用下一层backtrack，等待返回
    🟢 【层级3】 调用阶段 → path=[2,2], sum=4, start=0
    🔍 【层级3】 遍历i=0 → 尝试选数字2，当前sum=4
    ✅ 【层级3】 选数字2 → path=[2,2,2], sum=6
    🟡 【层级3】 暂停阶段 → 调用下一层backtrack，等待返回
      🟢 【层级4】 调用阶段 → path=[2,2,2], sum=6, start=0
      🔍 【层级4】 遍历i=0 → 尝试选数字2，当前sum=6
      🚫 【层级4】 排序剪枝 → 6+2=8 > 7，break循环
      🔴 【层级4】 返回阶段 → for循环结束，回到上一层
    🔴 【层级3】 返回阶段 → 从下一层返回，继续执行
    🔵 【层级3】 撤销阶段 → 撤销数字2 → path=[2,2], sum=4
    🔍 【层级3】 遍历i=1 → 尝试选数字3，当前sum=4
    ✅ 【层级3】 选数字3 → path=[2,2,3], sum=7
    🟡 【层级3】 暂停阶段 → 调用下一层backtrack，等待返回
      🟢 【层级4】 调用阶段 → path=[2,2,3], sum=7, start=1
      ✅ 【层级4】 找到有效组合 → [2,2,3]，result=[[2,2,3]]
      🔴 【层级4】 返回阶段 → 找到解，回到上一层
    🔴 【层级3】 返回阶段 → 从下一层返回，继续执行
    🔵 【层级3】 撤销阶段 → 撤销数字3 → path=[2,2], sum=4
    🔍 【层级3】 遍历i=2 → 尝试选数字7，当前sum=4
    🚫 【层级3】 排序剪枝 → 4+7=11 > 7，break循环
    🔴 【层级3】 返回阶段 → for循环结束，回到上一层
  🔴 【层级2】 返回阶段 → 从下一层返回，继续执行
  🔵 【层级2】 撤销阶段 → 撤销数字2 → path=[2], sum=2
  🔍 【层级2】 遍历i=1 → 尝试选数字3，当前sum=2
  ✅ 【层级2】 选数字3 → path=[2,3], sum=5
  🟡 【层级2】 暂停阶段 → 调用下一层backtrack，等待返回
    🟢 【层级3】 调用阶段 → path=[2,3], sum=5, start=1
    🔍 【层级3】 遍历i=1 → 尝试选数字3，当前sum=5
    🚫 【层级3】 排序剪枝 → 5+3=8 > 7，break循环
    🔴 【层级3】 返回阶段 → for循环结束，回到上一层
  🔴 【层级2】 返回阶段 → 从下一层返回，继续执行
  🔵 【层级2】 撤销阶段 → 撤销数字3 → path=[2], sum=2
  🔍 【层级2】 遍历i=2 → 尝试选数字7，当前sum=2
  🚫 【层级2】 排序剪枝 → 2+7=9 > 7，break循环
  🔴 【层级2】 返回阶段 → for循环结束，回到上一层
🔴 【层级1】 返回阶段 → 从下一层返回，继续执行
🔵 【层级1】 撤销阶段 → 撤销数字2 → path=[], sum=0
🔍 【层级1】 遍历i=1 → 尝试选数字3，当前sum=0
✅ 【层级1】 选数字3 → path=[3], sum=3
🟡 【层级1】 暂停阶段 → 调用下一层backtrack，等待返回
  🟢 【层级2】 调用阶段 → path=[3], sum=3, start=1
  🔍 【层级2】 遍历i=1 → 尝试选数字3，当前sum=3
  ✅ 【层级2】 选数字3 → path=[3,3], sum=6
  🟡 【层级2】 暂停阶段 → 调用下一层backtrack，等待返回
    🟢 【层级3】 调用阶段 → path=[3,3], sum=6, start=1
    🔍 【层级3】 遍历i=1 → 尝试选数字3，当前sum=6
    🚫 【层级3】 排序剪枝 → 6+3=9 > 7，break循环
    🔴 【层级3】 返回阶段 → for循环结束，回到上一层
  🔴 【层级2】 返回阶段 → 从下一层返回，继续执行
  🔵 【层级2】 撤销阶段 → 撤销数字3 → path=[3], sum=3
  🔍 【层级2】 遍历i=2 → 尝试选数字7，当前sum=3
  🚫 【层级2】 排序剪枝 → 3+7=10 > 7，break循环
  🔴 【层级2】 返回阶段 → for循环结束，回到上一层
🔴 【层级1】 返回阶段 → 从下一层返回，继续执行
🔵 【层级1】 撤销阶段 → 撤销数字3 → path=[], sum=0
🔍 【层级1】 遍历i=2 → 尝试选数字7，当前sum=0
✅ 【层级1】 选数字7 → path=[7], sum=7
🟡 【层级1】 暂停阶段 → 调用下一层backtrack，等待返回
  🟢 【层级2】 调用阶段 → path=[7], sum=7, start=2
  ✅ 【层级2】 找到有效组合 → [7]，result=[[2,2,3],[7]]
  🔴 【层级2】 返回阶段 → 找到解，回到上一层
🔴 【层级1】 返回阶段 → 从下一层返回，继续执行
🔵 【层级1】 撤销阶段 → 撤销数字7 → path=[], sum=0
🔴 【层级1】 返回阶段 → for循环结束，回到上一层
========== 执行结束 ==========
最终结果： [ [ 2, 2, 3 ], [ 7 ] ]

执行流程解析

以 candidates = [2,3,7], target = 7 为例：

  1. 选2 → path=[2], sum=2 → 钻到底（递归）
  2. 选2 → path=[2,2], sum=4 → 钻到底（递归）
  3. 选2 → path=[2,2,2], sum=6 → 钻到底（递归）
  4. 选2 → sum=8 > 7，剪枝，退回来
  5. 删掉2 → path=[2,2], sum=6 → 选下一个数3
  6. 选3 → path=[2,2,3], sum=7 ✅ 找到解，退回来
  7. 删掉3 → path=[2,2], sum=6 → 选下一个数7
  8. 剪枝，退回来 → path=[2], sum=2 → 继续尝试...
  9. 最终收集到 [[2,2,3],[7]]

三、回溯算法常见题型及解题方法

1. 组合问题

核心特征
  • 不考虑元素顺序，每个组合唯一（如[2,3]和[3,2]算同一个）
  • 用start参数控制"不回头选"，避免生成重复组合
  • 数字可重复选（组合总和）/不可重复选（组合），仅需调整start参数（重复选传i，不重复选传i+1）
LeetCode 题目详解
39. 组合总和

题目描述：

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次。
7 也是一个候选， 7 = 7。
所以这两种组合是唯一的答案。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

解决方案：

/**
 * 39. 组合总和
 * @param {number[]} candidates - 无重复元素的候选数组
 * @param {number} target - 目标和
 * @returns {number[][]} 所有符合条件的组合
 */
function combinationSum(candidates, target) {
  const res = [];
  candidates.sort((a, b) => a - b); // 排序便于剪枝

  function backtrack(path, sum, start) {
    // 终止条件：找到有效解
    if (sum === target) {
      res.push([...path]);
      return;
    }
    // 剪枝：和超过目标值
    if (sum > target) return;

    for (let i = start; i < candidates.length; i++) {
      const num = candidates[i];
      // 排序剪枝：后续数更大，无需继续
      if (sum + num > target) break;

      // 选数
      path.push(num);
      // 钻到底：数字可重复选，所以start仍为i
      backtrack(path, sum + num, i);
      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 0, 0);
  return res;
}

易错点：

  • 忘记排序导致剪枝失效
  • start参数传错（重复选传i，不重复选传i+1）
  • 忘记拷贝路径（[...path]）
40. 组合总和 II

题目描述：

给定一个候选人编号的集合 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

示例 1：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

解决方案：

/**
 * 40. 组合总和 II
 * @param {number[]} candidates - 可能包含重复元素的候选数组
 * @param {number} target - 目标和
 * @returns {number[][]} 所有符合条件的组合（不重复）
 */
function combinationSum2(candidates, target) {
  const res = [];
  candidates.sort((a, b) => a - b); // 排序便于剪枝和去重

  function backtrack(path, sum, start) {
    // 终止条件：找到有效解
    if (sum === target) {
      res.push([...path]);
      return;
    }
    // 剪枝：和超过目标值
    if (sum > target) return;

    for (let i = start; i < candidates.length; i++) {
      const num = candidates[i];

      // 去重剪枝：跳过重复元素（关键！）
      // i > start 确保同一层不选重复数字，但不同层可以选
      if (i > start && candidates[i] === candidates[i - 1]) {
        continue;
      }

      // 排序剪枝
      if (sum + num > target) break;

      // 选数
      path.push(num);
      // 钻到底：数字不可重复选，所以start传i+1
      backtrack(path, sum + num, i + 1);
      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 0, 0);
  return res;
}

易错点：

  • 去重逻辑错误：应该是i > start而不是i > 0（允许不同层选相同数字）
  • 忘记排序导致去重失效
77. 组合

题目描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解决方案：

/**
 * 77. 组合
 * @param {number} n - 范围 [1, n]
 * @param {number} k - 组合长度
 * @returns {number[][]} 所有可能的k个数的组合
 */
function combine(n, k) {
  const res = [];

  function backtrack(path, start) {
    // 终止条件：路径长度等于k
    if (path.length === k) {
      res.push([...path]);
      return;
    }

    // 剪枝：剩余可选数字不够
    // 还需要选 k - path.length 个数，从start到n还有 n - start + 1 个数
    // 如果 n - start + 1 < k - path.length，则无法凑够k个数
    if (n - start + 1 < k - path.length) return;

    for (let i = start; i <= n; i++) {
      // 选数
      path.push(i);
      // 钻到底：不重复选，所以start传i+1
      backtrack(path, i + 1);
      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 1);
  return res;
}

易错点：

  • 范围错误：应该是[1, n]，循环条件是i <= n而不是i < n
  • 忘记剪枝优化导致超时
216. 组合总和 III

题目描述：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1：

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

解决方案：

/**
 * 216. 组合总和 III
 * @param {number} k - 组合长度
 * @param {number} n - 目标和
 * @returns {number[][]} 所有符合条件的组合
 */
function combinationSum3(k, n) {
  const res = [];

  function backtrack(path, sum, start) {
    // 终止条件1：找到有效解（长度和和都满足）
    if (path.length === k && sum === n) {
      res.push([...path]);
      return;
    }
    // 终止条件2：长度已满但和不满足，或和已超
    if (path.length === k || sum >= n) return;

    // 剪枝：剩余可选数字不够
    if (9 - start + 1 < k - path.length) return;

    for (let i = start; i <= 9; i++) {
      // 剪枝：当前数加上已选和超过目标值
      if (sum + i > n) break;

      // 选数
      path.push(i);
      // 钻到底：数字不可重复选，所以start传i+1
      backtrack(path, sum + i, i + 1);
      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 0, 1);
  return res;
}

2. 排列问题

核心特征
  • 考虑元素顺序，每个排列唯一（如[1,2]和[2,1]算不同排列）
  • 用used数组控制"不重复选"，循环从0开始（允许选任意未选过的数字）
  • 含重复数字的排列（全排列II）需增加"去重剪枝"
LeetCode 题目详解
46. 全排列

题目描述：

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

解决方案：

/**
 * 46. 全排列
 * @param {number[]} nums - 不含重复数字的数组
 * @returns {number[][]} 所有全排列
 */
function permute(nums) {
  const res = [];
  const len = nums.length;
  const used = new Array(len).fill(false); // 标记哪些数字已使用

  function backtrack(path) {
    // 终止条件：路径长度等于数组长度
    if (path.length === len) {
      res.push([...path]);
      return;
    }

    // 遍历所有可选数字（排列从0开始，允许选任意未选过的数字）
    for (let i = 0; i < len; i++) {
      // 剪枝：跳过已选数字
      if (used[i]) continue;

      // 选数
      used[i] = true;
      path.push(nums[i]);

      // 钻到底
      backtrack(path);

      // 退回来→删掉这个数
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return res;
}

易错点：

  • 忘记使用used数组导致重复选同一个数字
  • 循环应该从0开始，不是从start开始（排列需要考虑所有位置）
47. 全排列 II

题目描述：

给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

解决方案：

/**
 * 47. 全排列 II
 * @param {number[]} nums - 可能包含重复数字的数组
 * @returns {number[][]} 所有不重复的全排列
 */
function permuteUnique(nums) {
  const res = [];
  const len = nums.length;
  const used = new Array(len).fill(false);
  nums.sort((a, b) => a - b); // 排序便于去重

  function backtrack(path) {
    // 终止条件：路径长度等于数组长度
    if (path.length === len) {
      res.push([...path]);
      return;
    }

    for (let i = 0; i < len; i++) {
      // 剪枝1：跳过已选数字
      if (used[i]) continue;

      // 剪枝2：去重（关键！）
      // 如果当前数字和前一个数字相同，且前一个数字未被使用，则跳过
      // 这确保相同数字按顺序使用，避免重复排列
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue;
      }

      // 选数
      used[i] = true;
      path.push(nums[i]);

      // 钻到底
      backtrack(path);

      // 退回来→删掉这个数
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return res;
}

易错点：

  • 去重逻辑错误：应该是!used[i - 1]而不是used[i - 1]
    • !used[i - 1]：前一个相同数字未被使用，说明我们在同一层尝试重复数字，应该跳过
    • used[i - 1]：前一个相同数字已被使用，说明我们在不同层，可以使用

3. 子集问题

核心特征
  • 找出所有可能的子集（包括空集）
  • 用start参数控制不回头选，无需严格终止条件（每次递归都记录路径）
  • 含重复数字的子集（子集II）需增加"去重剪枝"
LeetCode 题目详解
78. 子集

题目描述：

给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解决方案：

/**
 * 78. 子集
 * @param {number[]} nums - 不含重复元素的数组
 * @returns {number[][]} 所有子集
 */
function subsets(nums) {
  const res = [];

  function backtrack(path, start) {
    // 每次递归都记录路径（无需严格终止条件）
    res.push([...path]);

    for (let i = start; i < nums.length; i++) {
      // 选数
      path.push(nums[i]);

      // 钻到底：不重复选，所以start传i+1
      backtrack(path, i + 1);

      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 0);
  return res;
}

易错点：

  • 忘记在每次递归开始时记录路径（子集问题需要在每个节点都记录，不只是叶子节点）
90. 子集 II

题目描述：

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

解决方案：

/**
 * 90. 子集 II
 * @param {number[]} nums - 可能包含重复元素的数组
 * @returns {number[][]} 所有不重复的子集
 */
function subsetsWithDup(nums) {
  const res = [];
  nums.sort((a, b) => a - b); // 排序便于去重

  function backtrack(path, start) {
    // 每次递归都记录路径
    res.push([...path]);

    for (let i = start; i < nums.length; i++) {
      // 去重剪枝：跳过重复元素（关键！）
      // i > start 确保同一层不选重复数字，但不同层可以选
      if (i > start && nums[i] === nums[i - 1]) {
        continue;
      }

      // 选数
      path.push(nums[i]);

      // 钻到底：不重复选，所以start传i+1
      backtrack(path, i + 1);

      // 退回来→删掉这个数
      path.pop();
    }
  }

  backtrack([], 0);
  return res;
}

易错点：

  • 去重逻辑和组合总和II相同，但容易忘记排序

四、回溯算法核心优化：剪枝

剪枝是提升回溯效率的关键，常见剪枝策略：

  1. 提前终止：如组合总和中"路径和超过目标值直接返回"
  2. 排序剪枝：先排序候选数组，遇到"当前值+已选和>目标值"时，后续值更大，直接break
  3. 重复剪枝：如子集II/全排列II中，跳过重复元素（if (i > start && nums[i] === nums[i-1]) continue）
  4. 约束剪枝：如N皇后中，提前判断位置是否合法，不合法则跳过
  5. 数量剪枝：如组合问题中，剩余可选数字不够时直接返回

五、总结

  1. 核心思想：回溯 = 深度优先遍历 + 状态回退 + 剪枝，核心是"选→探→撤"
  2. 固定节奏：push（选数）→ 递归（钻深层）→ pop（擦脚印），抓住这个节奏就能解决所有回溯题
  3. 模板复用：
    • 组合/子集：用start参数避免重复，循环从start开始
    • 排列：用used数组避免重复选，循环从0开始
  4. 优化关键：剪枝是减少无效递归的核心，能让回溯效率提升一个量级

回溯算法看似复杂，但只要抓住"选→钻→退→删"这个固定节奏和"剪枝优化"这个核心，就能轻松应对各类回溯问题。建议从简单的组合问题入手，逐步过渡到排列、子集问题，多写多练就能融会贯通。

❌