回溯算法与剪枝

回溯是「暴力搜索 + 撤销选择」。它的通用性最强，优化空间几乎全在剪枝上——同样的骨架，剪枝写得好能从一个跑不动的指数级搜索，变成秒出答案。

一、选择、递归、撤销

回溯就是「做选择 → 递归 → 撤销选择」三步循环，配合两个判断：什么时候记录答案（满足结束条件）、什么时候跳过（不满足约束）。最容易写错的是第三步——忘记撤销会让 path 在兄弟分支之间串味，表现为答案莫名其妙变多或变长。

这套骨架之所以通用，是因为它把「枚举所有可能」这件事标准化了：不论求组合、排列还是所有路径，变的只是「选择集」和「结束条件」，循环结构不变。理解了这一点，新题只是换参数，不是换思路。

function backtrack(path, choices) {
  if (满足结束条件) {
    result.push([...path]) // 注意：必须拷贝，否则后面修改 path 会影响已存的结果
    return
  }
  for (const choice of choices) {
    if (不合法) continue // 剪枝
    path.push(choice)             // 做选择
    backtrack(path, 下一层的选择集)
    path.pop()                    // 撤销选择
  }
}

那行 result.push([...path]) 的拷贝必须点明：直接 push(path) 存的是引用，等回溯把 path 改掉，结果数组里全是空数组或最后的状态。这是新手最常见的坑。

二、组合与排列的差别

子集 / 组合与排列，写法不同，语义也不同。

组合 / 子集：不强调顺序，用 start 索引避免重复取用前面已选过的元素（元素不复用）。
排列：强调顺序，同一元素在不同位置算不同解，用 used 数组标记已选，而不是 start。

// 组合：用 start 避免重复（[1,2] 和 [2,1] 视为同一个）
backtrack(path, i + 1) // 下一层从 i+1 开始
// 排列：用 used 标记，允许同层换位置
if (used[i]) continue
used[i] = true
backtrack(path, used)
used[i] = false

子集与组合经常混为一谈：子集不要求顺序但允许「不选」，组合是从 n 个里取 k 个。它们的代码几乎一样，差别在结束条件——子集在每一层都可以「选或不选」，组合要数够 k 个才停。

组合用 start 索引、排列用 used 数组，两者语义不同，不能套同一套

三、同层去重的手法

去重有两种常见写法：排序后跳过相邻相同元素（同层里值相等的分支只走一次），或每层用 Set 记录本层已用过的元素。但「用 Set 过滤最终结果」是错的做法——那是在搜索完之后才去重，所有重复分支的算力已经花掉了，成本照付。正确做法是在搜索树上同层去重，让重复分支根本不走。

// 排序后，同层跳过相邻的相同元素
nums.sort((a, b) => a - b)
for (let i = start; i < nums.length; i++) {
  if (i > start && nums[i] === nums[i - 1]) continue // 同层已选过，跳过
  path.push(nums[i])
  backtrack(path, i + 1)
  path.pop()
}

去重要在搜索树上做，不要在结果上过滤

图：回溯的搜索树与同层剪枝——被剪掉的分支根本没被展开

四、提前判死的几种条件

剪枝的前提是先估算搜索空间。三类最常见：

可行性剪枝：当前和已超过目标，后面不用试了 → if (sum > target) return。
重复性剪枝：同一层里值相同的分支只走一次（通常先排序再跳过相邻相同元素）。
上下界剪枝：剩下的元素全取上也达不到目标，直接返回 → if (sum + rest < target) return。

// 组合总和类：排序后，超过目标直接 break（后续更大，必超）
nums.sort((a, b) => a - b)
for (let i = start; i < nums.length; i++) {
  if (sum + nums[i] > target) break // 后面更大，无需继续
  backtrack(path, sum + nums[i], i)
}

剪枝能砍掉指数级搜索里的绝大部分分支，但能砍多少取决于约束有多紧——约束越具体，能剪的越多。剪枝的本质是「提前承认这条路走不通」，把算力省给真正可能出解的分支。

想确认剪枝到底生效没有，最可靠的办法是给递归加一个调用计数器，比较加上前后的次数——差出一个数量级才算真的剪到了。如果加完判断计数几乎没变，多半是把约束写在了结果过滤上，而不是写进了搜索过程里。

剪枝值不值得做，数一下搜索树节点数就知道了：

let nodes = 0

function backtrack(path, start) {
  nodes++                       // 每次进入递归记一次
  if (path.length === k) { collect(path); return }
  for (let i = start; i < n; i++) {
    if (sum + nums[i] > target) break   // 剪枝：后面更大，必超
    path.push(nums[i]); backtrack(path, i + 1); path.pop()
  }
}

// 同一个用例分别注释掉 break 跑一遍，节点数常常是几百对几万的差别

复杂度上要有数：无剪枝的全排列是 O(n!)，子集枚举是 O(2ⁿ)，组合数是 O(C(n, k))。剪枝不改变最坏上界，但能把实际展开的节点数砍掉几个数量级——这也是同一道题「加剪枝前超时、加完 0ms」的原因。

五、为什么剪枝后完全不同

回溯通常是指数级，别指望靠常数优化救回来。能转成动态规划的问题（有重叠子结构、无顺序约束）优先转 DP，因为 DP 用记忆化把指数压成多项式。回溯的价值在于「没有更优模型时，它能保证不漏解」——慢，但正确。

一个实用判断：如果题目问「所有满足条件的方案」「全部路径」，基本是回溯；如果问「最多 / 最少 / 能否」，多半有 DP 或贪心更优。先定性再动手，能省大量时间。

能剪多少取决于约束有多紧，能转 DP 就别硬回溯

六、剪枝改变了搜索的规模

回溯不等于暴力枚举，剪枝能把指数级搜索里的绝大部分分支砍掉——这是它和纯暴力的分界线。

去重也不该用 Set 在最后过滤，那时成本已经产生了；正确做法是在搜索树上同层去重。

组合与排列的写法更不能通用：组合用 start 索引避免重复，排列用 used 数组，两者语义不同。

能剪多少取决于约束有多紧——约束越具体，能剪掉的越多；能转成 DP 的场景就别硬回溯。

想系统补一遍搜索类题目，OI Wiki 回溯法的归纳比题解站更适合建立框架。

一、选择、递归、撤销​

二、组合与排列的差别​

三、同层去重的手法​

四、提前判死的几种条件​

五、为什么剪枝后完全不同​