回溯（backtrack）算法

时间复杂度

分析回溯问题的时间复杂度，有一个通用公式：路径长度×搜索树的叶子数

叶子节点的数量很多时候和排列数或者组合数有关，涉及阶乘。

• 排列数定义

$$A_n^m = \underbrace{n \times (n-1) \times \cdots \times (n-m+1)}_{m \text{ 个因子}} = \frac{n!}{(n-m)!}$$

其实就是从下标开始往后乘 m 个数。例如：

$$A_5^2 = 5 \times 4 = \frac{5!}{3!}$$

• 组合数定义

$$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!} = \binom{n}{m}$$

也就是在排列数的基础上，再除以上标的阶乘即可。

答题模版/恢复现场

在回溯法解题的时候，我们往往是穷举所有可能性直到试出满足条件的那个。

在这个过程中，我们往往会用一个 path: number[] 亦或者 track: number[] 来记录单次的答案。 但是当往前走发现路不通的时候，我们还得走回来，像月光宝盒一样回到当初的状态，这个就是 恢复现场 亦或者 回溯 的过程。

例如在解决 N 皇后问题的时候，我们除了恢复了 path 数组，还恢复了三个 set。

path.push(i);
colSet.add(i);
diag1.add(d1);
diag2.add(d2);

backtrack(start + 1);

path.pop();
colSet.delete(i);
diag1.delete(d1);
diag2.delete(d2);

在回溯函数调用的前后十分的对称。

子集型

核心是决定每个位置“选”或者“不选”。

我们得想清楚决策树长什么样，核心的约束条件是什么，例如

• Leetcode 22. 括号生成（右括号数量要小于左括号）
• Leetcode 131. 分割回文串（选定位置割出的东西得是回文串）

时间复杂度

每个元素选或不选，复杂度是 $O(2^n)$。如果算上拷贝 path 的时间（长度为 $n$），则是 $O(n \times 2^n)$。

组合型

典型的，例如给定 [1, 2, 3, 4, 5] ，要返回所有的组合可能。

我们需要明白，对于组合数，[1, 2] 和 [2, 1 是同一个组合。所以，为了确保不能重复，我们的循环体里，起点 往往是递增的。

也就是，第一次循环，我们也许需要枚举 [1, 2, 3, 4, 5] ，第二次只需要枚举 [2, 3, 4, 5]。

这种情况下，我们给 backtrack 函数往往传一个参数标识起点。

一个常见的模板

function solution(n: number, k: number): number[][] {
  // 用来记录最终答案的数组
  const ans: number[][] = [];
  // 循环过程中的单次路径
  const path: number[] = [];
  function backtrack(start: number) {
    // 到某个条件的时候，我们可以获得一个可能的答案
    if ( ... ) {
      // 往往需要注意引用类型数据的问题
      ans.push([...path]);
      return;
    }
    for (let i = start; i <= n; i++) {
      path.push(i);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(1);
  return ans;
}

时间复杂度

取决于 $k$，最坏情况接近子集复杂度。

排列型

与组合型不同，[1, 2] 和 [2, 1] 是不同的排列。

所以，我们也许每次都要从最开始的起点开始枚举。

例如，当起点是 2 的时候，为了得到 [2, 1] ，我们还是要从 1 开始枚举。

另一个小细节：

为了确保循环中不出现重复元素，比如由于我们从 1 开始枚举，可能会再次枚举到 2， 这样就会出现 [2, 2] 的情况。为了避免这种情况，我们可能需要用哈希表来记录、判重。

还有一个不用哈希表的 swap 解法，在 Leetcode 46. 全排列中，我们直接就地交换元素，很讨巧：

function permute(nums: number[]): number[][] {
  const ans: number[][] = [];
  function backtrack(start: number) {
    if (start === nums.length) {
      ans.push([...nums]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      [nums[i], nums[start]] = [nums[start], nums[i]];
      backtrack(start + 1);
      [nums[start], nums[i]] = [nums[i], nums[start]];
    }
  }
  backtrack(0);
  return ans;
}

这个解法仅仅适用于 没有重复元素的数组。

时间复杂度

全排列是 $O(n!)$。算上拷贝时间，是 $O(n \times n!)$。