算法面试突击手册 —— 回溯

一、概念与特点

大白话 + 类比

回溯 = 走迷宫 + 带橡皮擦

你站在分岔路口，面前有三条路。先选第一条走下去。走到死胡同？退回来（回溯），把标记擦掉（撤销选择），再试第二条路。试完所有路，你就找到了所有通往出口的路径。

回溯算法的本质：在决策树的每个节点上，枚举所有可能的选择 → 深入探索 → 撤销选择（恢复现场）→ 试下一个选择。

回溯三要素：

  1. 路径：已经做过的选择（当前列表内容）
  2. 选择列表：当前还能选什么（未被使用的元素）
  3. 结束条件：走到决策树叶子了（路径满足条件）

回溯万能模板

void backtrack(路径, 选择列表, 其他参数) {
    if (满足结束条件) {
        result.add(new ArrayList<>(路径)); // ⚠️ 必须深拷贝！
        return;
    }

    for (选择 : 选择列表) {
        // 1. 做选择
        路径.add(选择);

        // 2. 进入下一层决策树
        backtrack(路径, 新的选择列表, ...);

        // 3. 撤销选择（"擦橡皮"）
        路径.remove(路径.size() - 1);
    }
}

子集 vs 排列 vs 组合——三类题的区别

这是回溯最核心的区分，搞混就全错：

类型结果有序？元素可重复选？如何避免重复代表题
子集/组合无序 [1,2]=[2,1]不可重复startIndex：每次从 i+1 开始78, 39(不重复), 131
排列有序 [1,2]≠[2,1]不可重复used[] 数组：标记哪些已选46
组合总和（可重复）无序可重复startIndex 但传 i 而不是 i+139

为什么子集用 startIndex 而排列用 used[]：

  • 子集：不希望 [1,2] 和 [2,1] 重复出现 → 规定只能往后选（startIndex）→ 天然去重
  • 排列：[1,2] 和 [2,1] 是不同的结果 → 每次从头开始看，用 used[] 标记已选的

识别信号词

  • “所有可能”、“所有组合”、“所有排列” → 回溯
  • “子集”、“幂集” → 子集型回溯
  • “组合总和”、“找出和为 target 的组合” → 组合型回溯
  • “分割”、“划分成” → 分割型回溯（枚举切点）
  • “N 皇后”、“单词搜索”、“解数独” → 二维回溯/约束满足

二、Hot 100 精讲题目

78. Subsets 子集

📌 返回数组所有可能的子集（幂集）。如 [1,2,3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

🔍 解题分析

核心思路：每个元素”选/不选”形成决策树。我们用 for 循环 + startIndex 写法（更通用）：

  1. 每个递归节点上，当前 path 本身就是一个有效子集，直接加入结果
  2. 从 startIndex 开始枚举，保证只看后面的元素，避免 [1,2] 和 [2,1] 重复

关键边界条件/易错点

易错点说明
每个节点都要收集不同于排列（走到底才收集），子集问题每个节点都是合法答案
必须 new ArrayList<>(path)直接 add(path) 会添加同一个引用，后续修改会污染结果
startIndex 的作用保证每次只从后面的元素中选，天然去重

手算推理：nums=[1,2,3]，回溯树：

                        []                       ← 加入
              /         |         \
            [1]        [2]        [3]            ← 加入
           /   \        |
        [1,2]  [1,3]  [2,3]                      ← 加入
         /
      [1,2,3]                                     ← 加入

✅ 完整 Java 实现

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    // 【关键】每个节点都对应一个子集，直接加入结果
    result.add(new ArrayList<>(path));

    // 从 start 开始，只看后面的元素（避免重复组合）
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                      // 选择 nums[i]
        backtrack(nums, i + 1, path, result);   // 下一层从 i+1 开始
        path.remove(path.size() - 1);           // 撤销选择
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(n × 2ⁿ) —— 2ⁿ 个子集，每个拷贝 O(n)
  • 空间复杂度：O(n) —— 递归栈深度 + path 大小

💡 记忆口诀

“每个节点都是答案，for 只往后看不回头”

46. Permutations 全排列

📌 返回数组所有可能的排列。如 [1,2,3] → [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

🔍 解题分析

核心思路：排列有序（[1,2] ≠ [2,1]），所以每次要从头开始选，但不能重复选同一个元素。用 used[] 数组标记。

子集 vs 排列的关键区别：

  • 子集用 startIndex：只往后选 → 天然不重复
  • 排列用 used[]：每次从头看 → 靠标记跳过已选的

关键边界条件/易错点

易错点说明
used 数组必须恢复撤销选择时 used[i] = false，否则后续分支选不到该元素
不能靠 startIndex排列需要在已选元素的”间隙”中插入新元素，只有从头循环才自然
path.size() == n走到底才收集（不像子集每个节点都收）

✅ 完整 Java 实现

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length]; // 标记哪些元素已被选用
    backtrack(nums, used, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path,
                       List<List<Integer>> result) {
    // 走到底：路径长度 == 数组长度 → 收集一个完整排列
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path)); // ⚠️ 深拷贝
        return;
    }

    // 从头开始选（排列需要有序），靠 used 数组去重
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // 已经选过了，跳过

        // 做选择
        used[i] = true;
        path.add(nums[i]);

        backtrack(nums, used, path, result);

        // 撤销选择（"擦橡皮"）
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

手算推理：nums=[1,2,3]

第 1 层：选 1 → used[0]=T, path=[1] 第 2 层：跳过 used[0]，选 2 → used[1]=T, path=[1,2] 第 3 层：跳过 used[0], used[1]，选 3 → used[2]=T, path=[1,2,3] → 收集 回溯：used[2]=F, path=[1,2]；循环结束 回溯：used[1]=F, path=[1]；选 3 → …

⏱ 复杂度分析

  • 时间复杂度：O(n × n!) —— n! 种排列，每个拷贝 O(n)
  • 空间复杂度：O(n) —— used 数组 + path + 递归栈

💡 记忆口诀

“used 数组记谁选了，从头循环靠标记去重，走到底才收集”

17. Letter Combinations of a Phone Number 电话号码的字母组合

📌 映射 2→"abc", 3→"def", ..., 9→"wxyz"。给定数字串，返回所有字母组合。如 "23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]

🔍 解题分析

核心思路：多叉树的回溯。每层 = 一个数字，该层的分支 = 该数字对应的几个字母。深度 = 数字串长度。

与子集/排列的区别：这不是”数组元素选或不选”，而是”每层从固定的几个字母中选一个”。每层的选择列表是独立的（由 digit 决定），不是全局数组。

关键边界条件/易错点

易错点说明
空字符串输入digits="" 时直接返回 []，不能返回 [""]
数字到字母的映射2→abc, 7→pqrs, 8→tuv, 9→wxyz（注意 7 和 9 有 4 个字母）
用 StringBuilder比 String 拼接效率高，回溯时用 deleteCharAt

✅ 完整 Java 实现

// 数字 → 字母的映射表（下标 2~9）
private static final String[] MAPPING = {
    "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits.isEmpty()) return result; // 空输入

    backtrack(digits, 0, new StringBuilder(), result);
    return result;
}

private void backtrack(String digits, int idx, StringBuilder path,
                       List<String> result) {
    // 处理完所有数字 → 收集结果
    if (idx == digits.length()) {
        result.add(path.toString());
        return;
    }

    // 当前数字对应的候选字母
    String letters = MAPPING[digits.charAt(idx) - '0'];

    // 枚举当前数字的每个可能字母
    for (char c : letters.toCharArray()) {
        path.append(c);                             // 选一个字母
        backtrack(digits, idx + 1, path, result);   // 处理下一个数字
        path.deleteCharAt(path.length() - 1);       // 撤销
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(3ᵐ × 4ⁿ) —— m 个 3 字母数字，n 个 4 字母数字
  • 空间复杂度：O(digits.length()) —— 递归栈深度

💡 记忆口诀

“每个数字一层，该层枚举对应字母，走到底就是答案”

39. Combination Sum 组合总和

📌 从数组中找出和为 target 的组合，元素可以重复选。如 candidates=[2,3,6,7], target=7 → [[2,2,3],[7]]

🔍 解题分析

核心思路：标准组合型回溯 + “可重复选”的变体。

  • 用 startIndex 保证结果无序
  • 可重复选的关键：递归时传 i 而不是 i+1（同一层可以重复选自己）
  • 用 currentSum 跟踪当前路径的和，超了就剪枝

为什么传 i 而不是 i+1：下轮从 i 开始，意味着当前元素可以被重复选。如果传 i+1，每个元素只能用一次。

为什么不会无限循环：因为 target 是有限的，当 currentSum > target 时会 return。

关键边界条件/易错点

易错点说明
先判断 target 再剪枝if (currentSum > target) return; 放在前面避免无限递归
去重依赖 startIndex如果不加 startIndex 从头开始，会重复出 [2,2,3] 和 [2,3,2]
剪枝优化可以提前排序 + if (currentSum + candidates[i] > target) break;

✅ 完整 Java 实现

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    // 排序便于剪枝
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] candidates, int target, int start, int currentSum,
                       List<Integer> path, List<List<Integer>> result) {
    // 找到了一个合法组合
    if (currentSum == target) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        // 当前值加上去就超了 → 后面的值更大，也一定超 → 剪枝
        if (currentSum + candidates[i] > target) break;

        path.add(candidates[i]);         // 选择 candidates[i]
        // ⭐ 关键：传 i 而不是 i+1，允许同一元素重复选
        backtrack(candidates, target, i, currentSum + candidates[i], path, result);
        path.remove(path.size() - 1);    // 撤销
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(n^(target/min)) —— 组合数可能极大
  • 空间复杂度：O(target/min) —— 最深路径长度

💡 记忆口诀

“有序组合用 start，可重复选就传 i（不+1），超了就剪”

22. Generate Parentheses 括号生成

📌 生成 n 对括号的所有合法组合。如 n=3 → ["((()))","(()())","(())()","()(())","()()()"]

🔍 解题分析

核心思路：这是”不用 for 循环”的回溯，因为每层只有两种固定选择（加 ( 或加 )），但需要剪枝保证合法性。

剪枝规则：

  • 只要 left < n，就可以加 ( —— 左括号数量没到上限
  • 只要 right < left，就可以加 ) —— 右括号不能超过左括号（否则无效）

为什么不是全排列：如果无脑加括号再验证，会有大量非法组合被生成后再丢弃。剪枝在生成阶段就杜绝了非法情况。

关键边界条件/易错点

易错点说明
right < left 不是 right < n合性规则是右括号不能多于左括号（在任意前缀中）
用 StringBuilder回溯需要高效的字符操作
卡特兰数合法括号组合数 = 第 n 个卡特兰数 C(n) = C(2n,n)/(n+1)

✅ 完整 Java 实现

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(n, 0, 0, new StringBuilder(), result);
    return result;
}

private void backtrack(int n, int left, int right, StringBuilder path,
                       List<String> result) {
    // 左括号和右括号都用完了 → 找到一个合法组合
    if (left == n && right == n) {
        result.add(path.toString());
        return;
    }

    // 分支1：加左括号 —— 只要还没到 n 就可以加
    if (left < n) {
        path.append('(');
        backtrack(n, left + 1, right, path, result);
        path.deleteCharAt(path.length() - 1); // 回溯
    }

    // 分支2：加右括号 —— 只有在右括号比左括号少时才能加
    // 保证任意前缀中左括号 ≥ 右括号（合法性条件）
    if (right < left) {
        path.append(')');
        backtrack(n, left, right + 1, path, result);
        path.deleteCharAt(path.length() - 1); // 回溯
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(4ⁿ/√n) —— 第 n 个卡特兰数的渐近复杂度
  • 空间复杂度：O(n) —— 递归栈深最多 2n

💡 记忆口诀

“左括号没满尽管加，右括号比左少才能加；两边都够 n 个就收集”

79. Word Search 单词搜索

📌 在 m×n 字符网格中找是否存在指定单词的路径。相邻 = 上下左右，同一格子不能重复用。如 board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED" → true

🔍 解题分析

核心思路（二维回溯）：

  1. 遍历每个格子作为起点
  2. DFS 在四个方向上匹配单词的每个字符
  3. 标记已访问：在 board 上直接修改（如改成 #），避免额外 visited 数组

为什么在 board 上直接标记：省去 visited 数组的空间，恢复时改回原字符。这是二维回溯的常用技巧。

关键边界条件/易错点

易错点说明
标记后必须恢复如果当前 DFS 路径失败，必须把标记改回去，让其他起点能用到这个格子
判断顺序先判断 idx == word.length()（匹配成功），再判断越界/字符不匹配
提前返回用 `
ASCII 范围board 是 char，word 也是 char，直接用 == 比较，不是 equals

✅ 完整 Java 实现

public boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;

    // 遍历每个格子作为搜索起点
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, i, j, 0)) {
                return true; // 找到了
            }
        }
    }
    return false; // 所有起点都试过了
}

// 从 (i, j) 开始，匹配 word 从 idx 开始的剩余部分
private boolean dfs(char[][] board, String word, int i, int j, int idx) {
    // 全部字符匹配完成 → 成功
    if (idx == word.length()) return true;

    // 越界 或 当前字符不匹配 → 此路不通
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
        || board[i][j] != word.charAt(idx)) {
        return false;
    }

    // 标记当前位置为已访问（改成特殊字符）
    char temp = board[i][j];
    board[i][j] = '#';

    // 向四个方向探索下一个字符
    boolean found = dfs(board, word, i + 1, j, idx + 1) // 下
                 || dfs(board, word, i - 1, j, idx + 1) // 上
                 || dfs(board, word, i, j + 1, idx + 1) // 右
                 || dfs(board, word, i, j - 1, idx + 1);// 左

    // 恢复标记（让其他起点的搜索能再次使用这个格子）
    board[i][j] = temp;

    return found;
}

⏱ 复杂度分析

  • 时间复杂度：O(mn × 3^L) —— 每个起点，每个位置最多 3 个分支（不会往回走），L 为单词长度
  • 空间复杂度：O(L) —— 递归栈深度等于单词长度

💡 记忆口诀

“每个格子当起点，四向搜索对字符；走过标 # 防回头，失败时恢复原字符”

131. Palindrome Partitioning 分割回文串

📌 将字符串分割成若干回文子串，返回所有分割方案。如 "aab" → [["a","a","b"],["aa","b"]]

🔍 解题分析

核心思路：回溯 + 回文判断。从 start 开始，枚举分割点 end。如果 s[start..end] 是回文，就切下来加入路径，递归处理剩余部分 s[end+1..]。

优化：用二维 DP 预处理所有子串是否是回文，避免每次重新判断。dp[i][j] 表示 s[i..j] 是否是回文。

dp[i][j] = s[i]==s[j] && (j-i≤2 || dp[i+1][j-1])

关键边界条件/易错点

易错点说明
start == n 时收集走到字符串末尾，说明当前分割方案完整
预处理回文区间 DP 填表可以减少大量重复判断
substring 的 end 参数s.substring(start, end+1) 左闭右开

✅ 完整 Java 实现

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();

    // 预处理：dp[i][j] = s[i..j] 是否回文
    // dp[i][j] = (s[i]==s[j]) && (j-i≤2 || dp[i+1][j-1])
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    for (int j = 0; j < n; j++) {        // j：右边界
        for (int i = 0; i <= j; i++) {   // i：左边界
            if (s.charAt(i) == s.charAt(j)
                && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }

    backtrack(s, 0, new ArrayList<>(), result, dp);
    return result;
}

private void backtrack(String s, int start, List<String> path,
                       List<List<String>> result, boolean[][] dp) {
    // 走到了字符串末尾 → 当前分割方案完成
    if (start == s.length()) {
        result.add(new ArrayList<>(path));
        return;
    }

    // 枚举所有可能的分割点 end
    for (int end = start; end < s.length(); end++) {
        if (dp[start][end]) { // [start..end] 是回文 → 切！
            path.add(s.substring(start, end + 1));       // 切下这段
            backtrack(s, end + 1, path, result, dp);     // 处理剩余
            path.remove(path.size() - 1);                // 回溯
        }
        // 不是回文 → 跳过这个分割点
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(n² + 2ⁿ) —— 预处理 O(n²)，最坏情况每个字符都是一个分割点
  • 空间复杂度：O(n²) —— 回文 DP 表

💡 记忆口诀

“枚举分割点，是回文就切一段，继续切剩余”

51. N-Queens N 皇后

📌 在 n×n 棋盘上放 n 个皇后，使其互不攻击（不同行、列、对角线）。返回所有合法的棋盘布局。如 n=4 → [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

🔍 解题分析

核心思路：逐行放置皇后（每行一个）。每行枚举列位置，用三个布尔数组快速判断合法性。

对角线编码的数学原理：

  • 主对角线（左上→右下 /）：同一主对角线上 row - col 为常数。如 (1,0) 和 (2,1) 的 row-col 都是 1。因为 row-col 范围是 [-(n-1), n-1]，加上偏移量 n 映射到 [1, 2n-1]
  • 副对角线（右上→左下 \）：同一副对角线上 row + col 为常数。如 (0,2) 和 (1,1) 的 row+col 都是 2。范围 [0, 2n-2]

为什么不是 8 方向判断：皇后走直线（横、竖、对角线），所以只需检查列 + 两条对角线。

关键边界条件/易错点

易错点说明
主对角线 d1 = row - col + n+n 防止索引为负
三个 boolean 数组大小cols[n], diag1[2n], diag2[2n]（因为 row+col 最大到 2n-2）
逐行放置可省略行标记因为每行只放一个皇后，行冲突自动避免

✅ 完整 Java 实现

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();

    boolean[] cols = new boolean[n];           // 列占用
    boolean[] diag1 = new boolean[2 * n];      // 主对角线 (row-col) 占用
    boolean[] diag2 = new boolean[2 * n];      // 副对角线 (row+col) 占用

    // 初始化棋盘
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');

    backtrack(0, n, board, cols, diag1, diag2, result);
    return result;
}

private void backtrack(int row, int n, char[][] board,
                       boolean[] cols, boolean[] diag1, boolean[] diag2,
                       List<List<String>> result) {
    // 所有行都放置完毕 → 收集棋盘
    if (row == n) {
        List<String> solution = new ArrayList<>();
        for (char[] r : board) solution.add(new String(r));
        result.add(solution);
        return;
    }

    // 在当前行枚举每一列
    for (int col = 0; col < n; col++) {
        // 对角线编码：
        // 主对角线（左上→右下 /）：row - col 相同
        int d1 = row - col + n; // +n 防止负数
        // 副对角线（右上→左下 \）：row + col 相同
        int d2 = row + col;

        // 当前位置被攻击 → 跳过
        if (cols[col] || diag1[d1] || diag2[d2]) continue;

        // 放皇后
        board[row][col] = 'Q';
        cols[col] = diag1[d1] = diag2[d2] = true;

        backtrack(row + 1, n, board, cols, diag1, diag2, result);

        // 撤皇后（回溯）
        board[row][col] = '.';
        cols[col] = diag1[d1] = diag2[d2] = false;
    }
}

⏱ 复杂度分析

  • 时间复杂度：O(n!) —— 第一行 n 个选择，第二行 ≤ n-1 个……
  • 空间复杂度：O(n) —— 递归栈 + 三个 boolean 数组

💡 记忆口诀

“逐行放皇后，三个数组锁列和对角线；row-col 和 row+col 定对角线编号”

494. Target Sum 目标和

📌 给数组每个数前面添 + 或 -，使表达式结果等于 target。求方案数。如 nums=[1,1,1,1,1], target=3 → 5

🔍 解题分析

方法一：回溯（暴力枚举）——每个数两种选择（+ 或 -），2ⁿ 条路径，走到底判断和。

方法二：转 0-1 背包 DP（推荐，O(n×sum)）

  • 设选为正的数的子集和为 P，总和为 sum
  • P - (sum - P) = target → P = (sum + target) / 2
  • 问题转化为：在数组中选一些数，使和等于 P → 标准 0-1 背包计数

什么时候选回溯 vs DP：时间复杂度 2ⁿ vs n×sum。n≤20 可以回溯，n 大用 DP。

关键边界条件

易错点说明
sum+target 为奇数P 必须是整数，奇数直接 return 0
target 绝对值 > sum不可能达成，return 0
回溯顺序先加后减 / 先减后加，顺序不重要

✅ 完整 Java 实现

// 回溯方法（适合 n 较小的情况，如 ≤20）
private int count = 0;

public int findTargetSumWays(int[] nums, int target) {
    dfs(nums, target, 0, 0);
    return count;
}

private void dfs(int[] nums, int target, int idx, int currentSum) {
    // 走到叶子节点：所有数字都处理完了
    if (idx == nums.length) {
        if (currentSum == target) {
            count++; // 这条路通到了 target
        }
        return;
    }

    // 分支1：当前数前面放 '+'
    dfs(nums, target, idx + 1, currentSum + nums[idx]);

    // 分支2：当前数前面放 '-'
    dfs(nums, target, idx + 1, currentSum - nums[idx]);
}

⏱ 复杂度分析

  • 时间复杂度：O(2ⁿ) —— 每个数字两种选择
  • 空间复杂度：O(n) —— 递归栈深度

💡 记忆口诀

“每个数正负两种选，走到底对 target 就算一个；n 大要转 DP（0-1 背包）”

🔜 上一章：09-二叉树 | 下一章：11-动态规划