递归与回溯

常见误区

很多人以为递归一定比迭代慢，实际上简单递归被 JIT 内联后差距很小，真正的限制是栈深度。

很多人以为把 path 直接 push 进结果就行，实际上存的是同一个数组引用，递归结束后全是空数组，必须 [...path]。

很多人以为重复结果可以在最后用 Set 过滤，实际上指数级搜索里提前剪枝能砍掉整棵子树，后置去重只是浪费。

常考题型

全排列 II

先排序让相同元素相邻，再用 used 同时处理"同一元素不能用两次"和"同一层相同值不重复选"。时间 O(n·n!)，空间 O(n)。

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);
  const res = [], path = [], used = new Array(nums.length).fill(false);
  const dfs = () => {
    if (path.length === nums.length) { res.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) continue;
      used[i] = true;
      path.push(nums[i]);
      dfs();
      path.pop();
      used[i] = false;
    }
  };
  dfs();
  return res;
}

组合总和

元素可以重复使用，所以下一层仍从 i 开始；排序后一旦 candidates[i] > rest 就直接 break，后面的更大更不可能凑出。时间 O(S·n)（S 为解的个数），空间 O(target / min)。

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const res = [], path = [];
  const dfs = (start, rest) => {
    if (rest === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > rest) break;
      path.push(candidates[i]);
      dfs(i, rest - candidates[i]);
      path.pop();
    }
  };
  dfs(0, target);
  return res;
}

括号生成

任意前缀中左括号数不小于右括号数，且总数不超过 n，这两个条件就是剪枝。时间 O(4ⁿ/√n)（第 n 个卡特兰数），空间 O(n)。

function generateParenthesis(n) {
  const res = [], path = [];
  const dfs = (open, close) => {
    if (path.length === 2 * n) { res.push(path.join('')); return; }
    if (open < n) { path.push('('); dfs(open + 1, close); path.pop(); }
    if (close < open) { path.push(')'); dfs(open, close + 1); path.pop(); }
  };
  dfs(0, 0);
  return res;
}

N 皇后

逐行放置，用三个集合分别记录已占用的列、主对角线 row - col 和副对角线 row + col，冲突就跳过。时间 O(n!)，空间 O(n²)（棋盘与结果）。

function solveNQueens(n) {
  const res = [], board = Array.from({ length: n }, () => '.'.repeat(n));
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const dfs = (row) => {
    if (row === n) { res.push([...board]); return; }
    for (let col = 0; col < n; col++) {
      const d1 = row - col, d2 = row + col;
      if (cols.has(col) || diag1.has(d1) || diag2.has(d2)) continue;
      cols.add(col); diag1.add(d1); diag2.add(d2);
      board[row] = board[row].slice(0, col) + 'Q' + board[row].slice(col + 1);
      dfs(row + 1);
      board[row] = '.'.repeat(n);
      cols.delete(col); diag1.delete(d1); diag2.delete(d2);
    }
  };
  dfs(0);
  return res;
}

关联阅读

• 动态规划：记忆化搜索就是给递归加上缓存，是两者的交界
• 排序算法：回溯去重几乎都要先排序
• 本目录说明：高级算法的整体学习路径