一、回溯算法

在一棵“决策树”上做 DFS，把所有合法路径都走一遍。

• 走 → 选择
• 走不通 → 撤销选择（回溯）
• 走到叶子 → 收集答案

本质：暴力 + 剪枝

---

二、回溯的统一模板

function backtrack(path, choices) {
  // 终止条件
  if (满足条件) {
    res.push(path.slice())
    return
  }

  // 遍历所有选择
  for (let i = 0; i < choices.length; i++) {
    // 剪枝（可选）
    if (不合法) continue

    // 做选择
    path.push(choices[i])

    // 递归
    backtrack(path, newChoices)

    // 撤销选择
    path.pop()
  }
}

---

三、回溯题型

1. 排列（Permutation）——顺序敏感

特点

• 123 和 321 算不同
• 每个元素 只能用一次

关键词

全排列、排列、不同顺序

模板重点

• 用 used[] 或 set
• 每一层：从所有没用过的数选

经典题

• LC 46 全排列
• LC 47 全排列 II（去重）

题解

// 46. 全排列
var permute = function(nums) {
  const res = [];
  const path = [];
  const used = new Array(nums.length).fill(false);
  const backTrack = () => {
    if (path.length === nums.length) {
      res.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 res
}

// 47. 全排列 （不重复）
var permuteUnique = function(nums) {
  const res = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  const backTrack = () => {
    if (path.length === nums.length) {
      res.push([...path]);

      return;
    }

    // 记录是否使用过；
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || map.get(nums[i])) continue;
      used[i] = true;
      path.push(nums[i]);

      backTrack();

      map.set(nums[i], true);

      path.pop();
      used[i] = false;
    }
  }

  backTrack();

  return res;
};

---

2. 组合（Combination）——顺序不敏感

特点

• [1,2] 和 [2,1] 算同一个
• 常见限制：选 k 个

关键词

组合、k 个、选几个

模板重点

• startIndex
• 下一层只能往后选

经典题

• LC 77 组合
• LC 216 组合总和 III

// 77.
var combine = function(n, k) {
  const res = [];


  const backTrack = (start, arr) => {
    if (arr.length === k) {
      res.push([...arr]);

      return;
    }

    for (let i = start; i <= n; i++) {
      arr.push(i);

      backTrack(i+1, arr);

      arr.pop();
    }
  }

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

// 216.
var combinationSum3 = function(k, n) {
  const min = (n) => {
    if (n >= 0) return n + min(n - 1);
    return 0;
  }
  const max = (n) => {
    const rest = 10 - n;
    if (rest === 10) return 0;
    return rest + max(n - 1);
  }

  if (n < min(k) || n > max(k)) return [];

  const res = [];

  const backTrack = (start, path) => {
    if (path.length === k) {
      const total = path.reduce((p, c) => p + c);
      if (total === n) res.push([...path]);

      return;
    }

    for (let i = start; i <= 9; i++) {
      path.push(i);

      backTrack(i + 1, path);

      path.pop();
    }
  }

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

---

3. 子集（Subset）——选 / 不选

特点

• 每个元素只有两种状态
• 元素用不用 都合法

关键词

子集、幂集

经典题

• LC 78 子集
• LC 90 子集 II（去重）

// 78.
var subsets = function(nums) {
  nums.sort((a, b) => a - b);
  const res = [];

  const backTrack = (start, path) => {
    res.push([...path]);

    if (start === nums.length) {
      return;
    }

    for (let i = start; i < nums.length; i++) {
      // 有相同元素判断
      // if (i > start && nums[i] === nums[i - 1]) continue;

      path.push(nums[i]);

      backTrack(i + 1, path);

      path.pop();
    }
  }

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

// 90.
var subsetsWithDup = function(nums) {
  nums.sort((a, b) => a - b)
  const res = [];

  const backTrack = (start, path) => {
    res.push([...path]);

    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;

      path.push(nums[i]);

      backTrack(i + 1, path);

      path.pop();
    }
  }

  backTrack(0, []);

  return res;
};

---

4. 组合总和（Combination Sum）——带约束搜索

特点

• 有 target
• 可重复 / 不可重复
• 数值约束剪枝很重要

关键词

总和、target、凑数

经典题

• LC 39 组合总和（可重复）
• LC 40 组合总和 II（不可重复）

// 39.
var combinationSum = function(candidates, target) {
  const res = [];

  const backTrack = (start, path, sum) => {
    if (sum === target) {
      res.push([...path]);
    }

    for (let i = start; i < candidates.length; i++) {
      const total = sum + candidates[i]
      if (total > target) continue;


      path.push(candidates[i]);

      backTrack(i, path, total);

      path.pop();
    }
  }

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

// 40.
var combinationSum2 = function(candidates, target) {
  candidates.sort((a, b) => a - b)
  const res = [];

  const backTrack = (start, path, sum) => {
    if (sum === target) res.push([...path]);

    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i - 1]) continue;
      const total = sum + candidates[i]

      if (total > target) break;

      path.push(candidates[i]);

      backTrack(i + 1, path, total);

      path.pop();
    }
  }

  backTrack(0, [], 0);

  return res
};

---

5. 字符串切割 / 拆分

特点

• 在字符串中切一刀 or 不切
• 常配合合法性判断

关键词

分割、切割、拆分字符串

经典题

• LC 131 分割回文串
• LC 93 复原 IP 地址

// 131.
var partition = function(s) {
  const res = [];

  const backTrack = (start, path) => {
    if (start === s.length) {
      res.push([...path]);
      return;
    }

    for (let i = start; i < s.length; i++) {
      const str = s.slice(start, i + 1);

      if (isStr(str)) {
        path.push(str);

        backTrack(i + 1, path);

        path.pop(str);
      }
    }
  }

  backTrack(0, [])
  return res
};

// 判断是否为回文
const isStr = (str) => {
  let left = 0, right = str.length - 1;

  while (left < right) {
    if (str[left] !== str[right]) return false;

    left++;
    right--;
  }

  return true;
}

// 93.
var restoreIpAddresses = function(s) {
  const res = [];

  const backTrack = (start, path) => {
    if(start === s.length && path.length === 4) {
      res.push(path.join('.'));

      return;
    }

    for (let i = start; i < s.length; i++) {
      const str = path.length === 3 ? s.slice(start) : s.slice(start, i + 1);

      const v = Number(str);
      if (v > 255 || (str.length > 1 && str.startsWith('0'))) continue;

      path.push(str);

      backTrack(i + 1, path);

      path.pop();
    }
  }

  backTrack(0, []);

  return res;
};

---

6. 棋盘类问题（二维回溯）

特点

• 二维
• 行、列、斜线约束

关键词

棋盘、皇后、数独

经典题

• LC 51 N 皇后
• LC 37 解数独（不会）

// 51.
var solveNQueens = function(n) {
  const res = [];

  const str = new Array(n).fill('.').join('');

  const dfs = (path) => {
    if (path.length === n) {
      res.push(path.map(pos => str.substring(0, pos) + 'Q' + str.substring(pos + 1)));
      return;
    }

    // 已用的列
    const cantUsedList = new Set([...path]);

    // 已占用的对角线
    for (let i = 0; i < path.length; i++) {
      if (path.length - i + path[i] < n) {
        cantUsedList.add(path.length - i + path[i])
      }
      if (path[i] + i - path.length >= 0) {
        cantUsedList.add(path[i] + i - path.length)
      }
    }


    for (let j = 0; j < n; j++) {
      if (cantUsedList.has(j)) continue;

      path.push(j);
      dfs(path);
      path.pop();
    }
  }

  dfs([]);

  return res;
};

---

7. 搜索路径类（DFS + 回溯）

特点

• 在图 / 矩阵中走路
• 不能走回头路

关键词

路径、单词搜索、迷宫

经典题

• LC 79 单词搜索
• LC 212 单词搜索 II

模板重点

// 79.
var _exist = function(board, word) {
    const m = board.length;
    const n = board[0].length;

    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (dfs(i, j, 0)) return true;
      }
    }

    return false;

    function dfs(i, j, idx) {
      if (idx === word.length) return true;

      if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== word[idx]) return false;

      const tmp = board[i][j];
      board[i][j] = '#'
      const found = dfs(i + 1, j, idx + 1) || dfs(i - 1, j, idx + 1) || dfs(i, j + 1, idx + 1) || dfs(i, j - 1, idx + 1);

      board[i][j] = tmp;

      return found;
    }
};