回溯怎么写？全排列、子集和组合总和怎样做？

简答

给你 [1, 2, 3]，要列出所有排列：第一位有 3 种选法，选定后第二位剩 2 种，第三位剩 1 种。把这些选择画出来就是一棵树，每条从根到叶子的路径就是一个排列。回溯就是用递归把这棵树走一遍。

写法固定成三步：做选择，把元素放进当前路径 path；递归，去做下一步选择；撤销选择，把刚放进去的元素弹出来，好让同一层试下一个元素。之所以要撤销，是因为整个搜索共用一个 path 数组，不撤销就会把上一条分支的选择带到下一条分支。

三类题的区别只在“下一步能选哪些”。全排列每一步可以选任何还没用过的元素，用 used 数组标记；子集和组合不关心顺序，[1, 2] 和 [2, 1] 算一个，所以用 start 下标规定只能往后选；组合总和允许同一个数重复用，递归时 start 传 i 而不是 i + 1。

要注意两点：收集结果时要存 path 的拷贝，比如 path.slice()，否则存进去的是同一个数组，最后会被撤销成空的；回溯本质上是穷举，全排列有 n! 个结果、子集有 2ⁿ 个，所以只能用在规模很小的输入上，能做的优化是剪枝，提前放弃不可能有解的分支。

全排列和子集

下面两个函数结构几乎一样，看它们在“下一步能选谁”上的不同：permute 每层都从 0 开始扫、靠 used 跳过已选的，subsets 从 start 开始往后扫。

function permute(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  function backtrack() {
    if (path.length === nums.length) {
      result.push(path.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]); // 做选择
      backtrack(); // 递归
      path.pop(); // 撤销选择
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

function subsets(nums) {
  const result = [];
  const path = [];

  function backtrack(start) {
    result.push(path.slice()); // 每个节点都是一个子集，包括空集
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

console.log(JSON.stringify(permute([1, 2, 3])));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
console.log(JSON.stringify(subsets([1, 2, 3])));
// [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
console.log(permute([]).length); // 1
console.log(subsets([]).length); // 1

为什么空数组的全排列和子集都是 1 个？空数组只有一种排列，就是什么都不放；子集里也只有空集。代码里 path.length 和 nums.length 一开始都是 0，permute 的终止条件立刻成立，收集一个 [] 后返回，所以结果是 [[]]，长度 1。

为什么一定要 path.slice()？result.push(path) 存进去的是同一个数组的引用。搜索结束时所有选择都被撤销了，path 变回空数组，result 里每一项都指向它，打印出来全是 []。slice() 不带参数时返回整个数组的浅拷贝，存下的是那一刻的快照。

子集为什么在函数一开头就收集，而不是在叶子收集？因为子集不要求长度固定，树上每个节点对应的路径都是一个合法子集：根节点是空集，往下一层是只有一个元素的子集，依此类推。全排列要求每个元素都用上，所以只在 path 满长时收集。

组合总和：同一个数可以重复选

题目是：给一组互不相同的正整数 candidates 和目标值 target，找出所有和为 target 的组合，同一个数可以选多次。看代码里两处和子集不同的地方：递归传的是 i，以及排序后的提前 break。

function combinationSum(candidates, target) {
  const sorted = candidates.slice().sort((a, b) => a - b);
  const result = [];
  const path = [];

  function backtrack(start, remain) {
    if (remain === 0) {
      result.push(path.slice());
      return;
    }
    for (let i = start; i < sorted.length; i++) {
      // 已经升序，当前数放不下，后面更大的数也放不下，整层剪掉
      if (sorted[i] > remain) break;
      path.push(sorted[i]);
      backtrack(i, remain - sorted[i]); // 传 i：下一步还能选自己
      path.pop();
    }
  }

  backtrack(0, target);
  return result;
}

console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7))); // [[2,2,3],[7]]
console.log(JSON.stringify(combinationSum([2, 3, 5], 8))); // [[2,2,2,2],[2,3,3],[3,5]]
console.log(JSON.stringify(combinationSum([2], 1))); // []

递归传 i 和传 i + 1 差在哪？传 i + 1 表示选过的数不能再选，这就是普通组合；传 i 表示下一步还能从自己开始选，于是能出现 [2, 2, 3]。但无论哪种，都不会回头选下标更小的数，所以 [3, 2, 2] 不会再出现一次。

break 为什么是安全的？数组已经升序，sorted[i] 比剩余值大，后面的数只会更大，这一层剩下的分支都不可能凑出解。这就是剪枝：不改变结果，只是少走没有希望的分支。没排序时只能写 continue，省下的工作就少很多。

[2] 凑 1 为什么返回空数组？2 一上来就比 1 大，被剪掉，没有任何路径能走到 remain === 0，所以一个结果也没有。

复杂度为什么这么高

全排列一共有 n! 个结果，每个结果拷贝一次要 O(n)，所以时间是 O(n × n!)；子集有 2ⁿ 个，时间是 O(n × 2ⁿ)。递归深度最多 n，额外空间是 path、used 和调用栈的 O(n)，不算存结果的部分。组合总和的结果数量取决于具体数字，没有简单的公式，剪枝能省多少也看数据。

所以回溯题的输入通常很小，比如 n 不超过 10 左右。题目只问“有多少种”而不需要列出每一种时，往往可以改用动态规划计数，见《动态规划怎么入门？爬楼梯和最长递增子序列怎样做？》。

常见追问

输入里有重复数字，全排列怎样去重？

先排序，让相同的数挨在一起。然后在循环里加一条：if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue。意思是相同的几个数必须按从左到右的顺序使用，前一个还没用时不能先用后一个，这样同一层就不会把相同的数各选一次，产生重复的排列。

回溯和深度优先搜索是什么关系？

回溯就是在选择树上做深度优先搜索，多出来的是“撤销选择”这一步。普通的 DFS 遍历一棵已有的树，节点状态不用恢复；回溯的树是边走边构造的，所有分支共用一份 path，所以离开一个节点时必须把状态还原。

递归太深会不会爆栈？

回溯的递归深度等于路径长度，也就是最多 n 层，而 n 本来就很小，一般不会爆栈。真正的瓶颈是结果数量带来的时间，不是栈深度。