Go back

LeetCode Hot 100——回溯篇（选择-递归-撤销、剪枝）

LeetCode Hot 100 · 回溯篇

回溯（Backtracking）是面试里「手撕」频率最高的题型之一。它的核心思想只有一句话：在递归树的每一个节点上，尝试每一种「选择」，递归到下一层，递归返回后再「撤销」这个选择，从而穷举出所有解，并在过程中用「剪枝」砍掉注定不可能的分支。

面试手撕时，先把下面这个模板背熟，90% 的回溯题都能套：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径的拷贝);   // 一定要拷贝，不能直接存引用
        return;
    }
    for (选择 : 选择列表) {
        做选择;                  // 把选择加入路径，更新状态
        backtrack(路径, 选择列表);
        撤销选择;                // 把刚才的选择撤掉，恢复现场
    }
}

回溯题的三个灵魂：

  1. 路径：已经做出的选择（通常用 path / StringBuilder / 数组承载）。
  2. 选择列表：当前还能做的选择（靠 index / used / 剩余计数 等状态限定）。
  3. 结束条件：何时把路径收进结果。

本篇文章把 Hot 100 里的 8 道回溯题挨个拆解：题意 → 难点易错点 → 暴力解法 → 最优解法（含复杂度逐步推导）→ 多解法对比 → CodeTop 真实变体。每一题的「题目本质」和「现实类比」都标在题意里，帮你面试时把思路讲得形象。

46. 全排列

题意

给定不含重复数字的数组 nums，返回它所有可能的全排列。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

题目本质：回溯 + used 标记——每次从「还没被选过」的元素里挑一个放进路径，路径长度等于 nums.length 时收集，回溯时撤销（移除最后元素、恢复 used）。

现实类比：排队照相。n 个人排 n 个位置，每次选一个还没站好位的人站下一个位置，全站好就拍照，再换人重排。

难点与易错点

  1. 必须用 used 标记：如果不用 used 数组，每个位置都会把「所有元素」再遍历一遍，导致同一元素被反复选，出现 [1,1,1] 这类非法排列。而且回溯时 used[i] 一定要同步恢复成 false，漏恢复会直接漏掉大量合法解。
  2. 收集时必须拷贝：result.add(new ArrayList<>(path)) 而不是 result.add(path)。path 对象后续会被回溯不断修改，直接存引用会让所有已收集的结果都指向同一个最终为空的列表。
  3. 边界：nums 只有一个元素时答案是 [[1]]（结果里要包一层 list）；空数组按题意不会出现，但防御性判断一下更稳。

解法一：暴力 / 直观

最直观的写法就是上面说的 used 数组回溯：每个位置遍历整个数组，跳过已选元素。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private Deque<Integer>      path   = new ArrayDeque<>();
    private boolean[]           used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtrack(nums);
        return result;
    }

    private void backtrack(int[] nums) {
        // 递归出口：路径长度等于 nums 长度，找到一个完整排列
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path)); // 拷贝一份加入结果
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue; // 跳过已选元素

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

            backtrack(nums);

            // 撤销选择（回溯核心）
            path.removeLast();
            used[i] = false;
        }
    }
}

复杂度（逐步推导）：全排列一共有 n! 个结果。递归树叶子节点数是 n!，每个叶子要把长度为 n 的 path 拷贝一份（O(n)），所以总时间 O(n × n!)。空间方面，递归深度最大 n，used 数组 O(n)，path 最大 O(n)，所以空间 O(n)。

瓶颈：每个位置都要从头扫描一遍 used 数组，且需要额外维护 used 和 path 两个结构，常数偏大；查重本身是 O(1)，瓶颈主要在「额外空间」和「拷贝开销」上。

解法二：优化 / 最优

用**原地交换法（swap）**替代 used 数组：把「已选集合」和「未选集合」在数组内部用下标分界，选第 first 位时，把 [first, n) 里的每个元素依次交换到 first 位置，递归处理 first+1，回来再换回。这样不需要 used 数组，也不需要 path。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, 0);
        return result;
    }

    // first 之前是已排好的前缀，first 之后是待排区
    private void backtrack(int[] nums, int first) {
        // 递归出口：first 走到末尾，nums 就是一个完整排列
        if (first == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) list.add(num); // 快照当前数组
            result.add(list);
            return;
        }

        for (int i = first; i < nums.length; i++) {
            swap(nums, first, i);   // 把 nums[i] 换到 first 位，即「选 nums[i]」
            backtrack(nums, first + 1);
            swap(nums, first, i);   // 回溯：换回来，恢复现场
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

复杂度（逐步推导）：结果数量不变，仍是 n! 个叶子节点。每个叶子收集时要遍历 nums 一次构造 list，O(n)，所以时间仍是 O(n × n!)。空间上：递归深度 O(n)（递归栈），数组本身原地修改，省掉了 used 数组和 path 队列，空间 O(n)，常数更小。

多解法对比

解法时间空间适用场景
used 数组回溯O(n × n!)O(n)最直观，面试第一反应，易讲清
swap 交换法O(n × n!)O(n)（常数更小）追求省空间、原地操作；但会打乱原数组，需注意是否允许修改入参

本题约束下 n 通常 ≤ 6~8，两者都能过。手撕时先写 used 法（最稳妥、最好讲），再提 swap 法作为空间优化，能体现你的层次感。

CodeTop 变体

78. 子集

题意

给你元素互不相同的整数数组 nums，返回所有可能的子集（幂集），结果不含重复子集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

题目本质：「选 / 不选」决策树（回溯）——对每个元素做「选」或「不选」的决策，走到数组末尾收集路径；也可以「从 index 开始选」，每进入一层递归就把当前路径收进结果。

现实类比：购物清单。对每件商品做决定「买」或「不买」，所有可能的购买方案就组成了幂集。

难点与易错点

  1. 收集时机：子集的特点是有 2^n 个结果，每个递归节点都是合法子集（包括空集），必须在进入递归时立即收集，而不是等叶子。漏掉空集或漏收中间状态是最常见的错。
  2. 去重靠 index：循环从 index 开始、递归传 i + 1，保证「只往后选、不往回选」，才能避免出现 [1,2] 和 [2,1] 这种重复。写成从 0 开始就会重复。
  3. 回溯 remove：path 是 ArrayList，回溯时 remove(path.size() - 1) 移除最后一个，注意别 remove 错位置。

解法一：暴力 / 直观（位运算枚举）

子集最直观的思路其实是二进制枚举：n 个元素，每个元素「在 / 不在」子集里对应一个二进制位，于是 0 ~ 2^n - 1 这 2^n 个整数一一对应所有子集。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        // 枚举 0 ~ 2^n - 1 的所有状态
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                // 第 i 位为 1，说明该子集包含 nums[i]
                if ((mask & (1 << i)) != 0) {
                    path.add(nums[i]);
                }
            }
            result.add(path);
        }
        return result;
    }
}

复杂度（逐步推导）：外层循环 2^n 次，内层每个 mask 都要扫描 n 个位，所以时间 O(n × 2^n)；空间主要是单个 path，O(n)。

瓶颈：思路最简单，但受限于 int 只有 32 位，n 超过 31 就溢出（本题 n ≤ 10 没问题）；更重要的是它写死了「枚举所有状态」，无法迁移到「含重复元素去重」「固定大小组合」等变体，通用性差。

解法二：优化 / 最优（回溯）

用「从 index 开始选」的回溯法，通用性强，也是后续所有组合类题的基础模板。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer>       path   = new ArrayList<>();

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

    private void backtrack(int[] nums, int index) {
        // 每进入递归，当前 path 就是一个合法子集（含空集）
        result.add(new ArrayList<>(path));

        // 从 index 开始选，保证子集不重复（不往回选）
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

复杂度（逐步推导）：决策树一共 2^n 个节点（每个元素对应「选/不选」两个分支，n 层展开）。每个节点都要把 path 拷贝一份进结果，平均路径长度 O(n)，所以时间 O(n × 2^n)。空间：递归深度最坏 O(n)，path 最大 O(n)，所以 O(n)。

💭 思考：位运算枚举最直观，为什么面试更该写回溯？——位运算的思路是「每个元素在/不在对应一个二进制位」，0 ~ 2^n-1 枚举完即可，但它写死了「枚举所有状态」，一旦要「去重」「固定大小组合 k」就改不动。回溯用 index 控制「只往后选」，天然把「组合不重复」这件事内化在递归结构里，是「子集/组合/排列」一整族的统一骨架。看到「枚举所有子集/组合」这类信号，先想到回溯模板（写一个会一串），位运算只当作「n 很小且只求子集」时的速解。

多解法对比

解法时间空间适用场景
位运算枚举O(n × 2^n)O(n)n 很小、只求子集时最简洁
回溯（选/不选）O(n × 2^n)O(n)通用模板，可平滑扩展到子集 II、组合等变体

本题约束下（n ≤ 10）两种都秒过。面试手撕优先写回溯，因为它是一整套「组合/子集/排列」题的统一骨架，写一个会一串。

CodeTop 变体

17. 电话号码的字母组合

题意

给定仅包含数字 2-9 的字符串 digits，返回它能表示的所有字母组合（九宫格映射，顺序任意）。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

题目本质：多叉递归枚举——每一位数字对应一组字母，逐位选择当前数字的某个字母，递归到下一位，处理完所有位时收集。

现实类比：九宫格暴力穷举。每个按键按下后跳到下一个按键，把所有可能的字母序列都枚举出来。

难点与易错点

  1. 空字符串边界：digits 为空时必须返回 []，不能返回 [""]。很多人习惯初始化 result 里放一个空字符串，忘了对空输入做特判。
  2. 映射表下标对齐：'0' 和 '1' 要占位成空字符串（PHONE_MAP[0]、PHONE_MAP[1] 都是 ""），否则 digits.charAt(index) - '0' 取下标会错位。
  3. StringBuilder 回溯：字符串结果用 StringBuilder 拼接，回溯时用 deleteCharAt(sb.length() - 1) 删除最后一个字符，忘记删除会污染后续分支。

解法一：暴力 / 直观（迭代扩展）

不递归，用一个列表逐位「展开」：初始一个空前缀，每处理一个数字，就把当前所有前缀 × 该数字的字母组，生成新的前缀集合。

class Solution {
    private static final String[] MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.isEmpty()) return result; // 空输入返回 []

        result.add(""); // 初始空前缀

        for (char digit : digits.toCharArray()) {
            String letters = MAP[digit - '0'];
            List<String> next = new ArrayList<>();
            // 每个已有前缀 × 当前字母组
            for (String prefix : result) {
                for (char c : letters.toCharArray()) {
                    next.add(prefix + c); // 每次拼接产生新字符串
                }
            }
            result = next;
        }
        return result;
    }
}

复杂度（逐步推导）：设 digits 长度 n，每位最多 4 个字母（数字 7、9 对应 4 个）。结果数量最多 4^n 个，每个结果长度为 n，构造每个结果耗时 O(n)，时间 O(4^n × n)。空间：显式保存了每一层的所有中间前缀，最坏 O(4^n)。

瓶颈：prefix + c 每次都新建字符串、整体拷贝前缀，且中间结果全部驻留内存，空间从 O(n) 膨胀到 O(4^n)，内存消耗大。

解法二：优化 / 最优（回溯）

用 StringBuilder 复用同一段缓冲区，DFS 递归逐位选择。

class Solution {
    private static final String[] PHONE_MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    private List<String>  result = new ArrayList<>();
    private StringBuilder sb     = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return result;
        backtrack(digits, 0);
        return result;
    }

    private void backtrack(String digits, int index) {
        // 所有位数字处理完，收集结果
        if (index == digits.length()) {
            result.add(sb.toString());
            return;
        }

        String letters = PHONE_MAP[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            sb.append(c);
            backtrack(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
    }
}

复杂度（逐步推导）：递归树最多 4^n 个叶子（每位最多 4 个分支、深度 n），每个叶子收集时 sb.toString() 拷贝一次，O(n)，时间 O(4^n × n)。空间：递归深度 O(n)，StringBuilder 复用同一块缓冲区 O(n)，不再需要保存所有中间前缀，所以空间 O(n)（不计结果集）。

多解法对比

解法时间空间适用场景
迭代扩展O(4^n × n)O(4^n)思路直白，但内存占用大
回溯O(4^n × n)O(n)空间更优，也是通用套路

本题约束下 digits 长度 ≤ 4，结果最多 4^4 = 256 个，两种都能过；但回溯空间 O(n) 明显优于迭代的 O(4^n)，且是面试的标准写法。

CodeTop 变体

39. 组合总和

题意

给你不含重复元素的整数数组 candidates 和目标整数 target，找出所有数字之和等于 target 的不同组合（候选数可重复使用）。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

题目本质：回溯 + 剪枝——每次从 [index, n) 里选，候选数可重复选（递归时 index 不加 1），remain < 0 时剪枝；排序后 candidates[i] > remain 时可以 break 提前剪枝。

现实类比：找零方案。用面额为 candidates 的零钱凑出 target，每种面额可以无限用，找出所有不重复的方案。

难点与易错点

  1. 去重关键在 index：递归传 i（不是 i + 1）才允许重复使用当前元素；同时循环从 index 开始、传 i，保证「只往后选」，才能避免 [2,3] 和 [3,2] 这种重复组合。这两点缺一不可。
  2. 剪枝用 break 不是 continue：排序后 candidates[i] > remain 时，i 及之后的所有元素都更大，应该 break 直接结束本层循环；写成 continue 虽然也能过（靠 remain < 0 兜底），但会多走很多无效分支。
  3. remain 的传递：递归时传 remain - candidates[i]，而不是在循环外修改 remain；回溯时 path 要 remove 最后一个。

解法一：暴力 / 直观（不排序、不剪枝）

最简单的回溯：不做排序，只靠 remain < 0 自然返回，把「超标的」分支交给下一层递归去兜底。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer>       path   = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, 0, target);
        return result;
    }

    private void backtrack(int[] candidates, int index, int remain) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (remain < 0) return; // 超了，自然返回（不剪枝，靠这里兜底）

        for (int i = index; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtrack(candidates, i, remain - candidates[i]); // 传 i 允许重复使用
            path.remove(path.size() - 1);
        }
    }
}

复杂度（逐步推导）：递归树最坏情况下，每层选最小元素 min，最多能选 T/min 层（T 为 target），每层分支最多 n 个，所以上界 O(n^(T/min))；空间是递归深度，最坏 O(T/min)。

瓶颈：不排序就无法提前判断「这个候选已经超过剩余目标了」，会一路递归到 remain < 0 才返回，大量时间浪费在明显超标的候选上，常数非常大。

解法二：优化 / 最优（排序 + break 剪枝）

先对 candidates 排序，这样一旦 candidates[i] > remain，后面所有元素都更大，直接 break 砍掉整条尾巴。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer>       path   = new ArrayList<>();

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

    private void backtrack(int[] candidates, int index, int remain) {
        if (remain == 0) {
            result.add(new ArrayList<>(path)); // 找到合法组合
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            // 当前候选数已超过剩余目标，后面的更大，直接剪枝
            if (candidates[i] > remain) break;

            path.add(candidates[i]);
            backtrack(candidates, i, remain - candidates[i]); // 传 i（可重复使用）
            path.remove(path.size() - 1); // 回溯
        }
    }
}

复杂度（逐步推导）：递归树每个节点做一次选择，最坏高度是 T/min（每次都选最小元素 min），每层分支数最多 n，所以时间上界仍是 O(n^(T/min))。空间：递归深度 + path 最坏 O(T/min)。排序 O(n log n) 相对主项可忽略。

优化体现在常数：break 剪枝让「candidates[i] > remain」的整条分支不再展开，省掉了大量注定失败的 remain < 0 递归，实际运行速度比解法一快一个量级。

💭 思考：为什么「排序 + break」比「不排序 + 靠 remain<0 兜底」快一个量级？——时间复杂度公式虽然一样，差别在常数。不排序时，一个候选已经超过剩余目标，还要一路递归到 remain < 0 才返回，把整棵注定失败的子树走完；排序后，一旦 candidates[i] > remain，后面的元素只会更大，break 直接砍掉整条尾巴。这就是「剪枝砍掉的不是复杂度阶数，而是大量注定失败的分支」。看到「组合/子集 + 候选有序」的信号，第一反应就是先排序再剪枝——排序的 O(n log n) 成本换来常数上的量级提速。

多解法对比

解法时间空间适用场景
不排序、不剪枝O(n^(T/min))，常数大O(T/min)只求写对，不 care 效率
排序 + break 剪枝O(n^(T/min))，常数小O(T/min)面试标准解，剪枝是加分点

本题约束下 target 可能较大，剪枝的价值明显。面试一定要写排序 + break 剪枝，「剪枝」是这道题的题眼。

CodeTop 变体

22. 括号生成

题意

给定 n 代表括号对数，返回所有有效的括号组合。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

题目本质：按规则回溯——用「剩余左括号数 left」和「剩余右括号数 right」约束选择：left > 0 时可以加 (；right > left 时（说明有未闭合的左括号）才可以加 )。

现实类比：打字机输入括号。左括号库存还有就能打左括号；当右括号库存比左括号多时（说明有未匹配的左括号在等你闭合），才能打右括号。

难点与易错点

  1. 合法性条件：任何前缀中右括号数都不能超过左括号数。回溯里写成 right > left 才允许加 )（右括号剩余必须比左括号剩余多，表示前面有未闭合的左括号）。写成 right > 0 就会生成 ())... 这类非法串。
  2. 两个分支各自撤销：( 和 ) 是两个独立的 append + delete 对，共用同一个 StringBuilder，每个分支递归返回后都要 deleteCharAt，漏一个就污染后续分支。
  3. 边界：n == 1 返回 ["()"]；n == 0 按题意不会出现，但可防御性返回 [""]。

解法一：暴力 / 直观（枚举所有序列再校验）

最笨的思路：生成长度为 2n、由 ( 和 ) 组成的所有序列，共 2^(2n) 个，再逐个校验是否合法。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] cur = new char[2 * n];
        generateAll(cur, 0, result);
        return result;
    }

    // 生成长度 2n 的所有 '(' / ')' 序列
    private void generateAll(char[] cur, int pos, List<String> result) {
        if (pos == cur.length) {
            if (valid(cur)) result.add(new String(cur)); // 校验合法才收
            return;
        }
        cur[pos] = '(';
        generateAll(cur, pos + 1, result);
        cur[pos] = ')';
        generateAll(cur, pos + 1, result);
    }

    // 校验括号序列是否合法：任意前缀右括号不能多于左括号
    private boolean valid(char[] cur) {
        int balance = 0;
        for (char c : cur) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false; // 右括号多于左括号，非法
        }
        return balance == 0;
    }
}

复杂度（逐步推导）：序列总数 2^(2n) = 4^n 个，每个序列 valid 校验要扫一遍长度 2n，O(n)，所以时间 O(4^n × n)；空间递归深度 O(n)。

瓶颈：4^n 个序列里绝大多数都是非法的（合法数量只有卡特兰数 4^n / n^(3/2) 量级），却要逐个生成再逐个校验，做了海量无用功。

解法二：优化 / 最优（按规则回溯剪枝）

用 left/right 两个剩余计数在生成过程中就剪掉非法分支，只走合法前缀。

class Solution {
    private List<String>  result = new ArrayList<>();
    private StringBuilder sb     = new StringBuilder();

    public List<String> generateParenthesis(int n) {
        backtrack(n, n);
        return result;
    }

    // left: 剩余可用左括号数，right: 剩余可用右括号数
    private void backtrack(int left, int right) {
        if (left == 0 && right == 0) {
            result.add(sb.toString()); // 括号全部使用完，合法组合
            return;
        }

        if (left > 0) { // 还有左括号可用，就能加 '('
            sb.append('(');
            backtrack(left - 1, right);
            sb.deleteCharAt(sb.length() - 1);
        }

        if (right > left) { // 右括号剩余必须比左括号多，才能加 ')'
            sb.append(')');
            backtrack(left, right - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

复杂度（逐步推导）：合法括号序列的数量是第 n 个卡特兰数 C_n = 1/(n+1) · C(2n, n)，其渐近增长约为 4^n / (n^(3/2) · √π)，主项记作 O(4^n / √n)。回溯只沿着合法前缀走，节点数即 C_n 量级；每个节点 O(1) 的 append/delete，收集时 sb.toString() 拷贝一次 O(n)，所以时间 O(4^n / √n)（严格说再乘 n，但面试主项记这个）。空间：递归深度最坏 O(2n) = O(n)。

对比：解法一 O(4^n × n)，解法二 O(4^n / √n)，把「生成所有 + 校验」降为「生成过程即保证合法」，剪枝效果显著。

💭 思考：为什么「生成所有再校验」要淘汰，而「生成过程即保证合法」是对的？——暴力版先造出 4^n 个序列再逐个 valid 校验，但绝大多数序列都是非法的（合法数量只有卡特兰数级），等于海量无用功。优化方向是把合法性前置到每一步：用「剩余左括号数 left」和「剩余右括号数 right」约束分支——left > 0 才能加 (，right > left 才能加 )（右括号剩余必须更多，说明前面还有未闭合的左括号在等它）。看到「生成满足某约束的所有序列」这类信号，就该想「能不能在递归途中就把非法分支剪掉」，而不是「先全生成再过滤」。

多解法对比

解法时间空间适用场景
枚举 + 校验O(4^n × n)O(n)只求写对，n 很小时可接受
按规则回溯剪枝O(4^n / √n)O(n)面试标准解，剪枝是题眼

本题约束 n ≤ 8，暴力也能过，但面试手撕必须写回溯剪枝，right > left 这个条件是被追问最多的点。

CodeTop 变体

79. 单词搜索

题意

给定 m x n 字符板和字符串 word，判断 word 是否存在于网格中（相邻格子水平或垂直相邻，每个格子只能用一次）。

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

题目本质：DFS + 回溯 + visited 原地标记——从每个格子尝试出发，沿四方向匹配单词字母，已用格子改成特殊标记防止重复使用，回溯时恢复。

现实类比：迷宫寻路。出发点对准单词第一个字母，每步往四方向走，走到能匹配下一字母的格子就踩过去（标记），走不通就退回来（回溯）。

难点与易错点

  1. 必须标记 + 必须恢复：不标记会走回头路死循环；但标记不能是「全局永久」的——不同路径可能复用同一格子，所以回溯时必须恢复。用原地改 board[r][c] = '#' 比额外 visited 数组更省空间。
  2. 判断顺序：先判断 idx == word.length()（匹配完成）再判断越界/已访问/字符不匹配。顺序反了会在 idx 越界后还去访问 word.charAt(idx) 导致数组越界。
  3. 提前剪枝：可以先统计 board 中每个字符的数量，若某字符在 board 中的数量少于它在 word 中的数量，直接返回 false，能大幅加速，是面试的加分点。

解法一：暴力 / 直观（DFS + 显式 visited 数组）

最直观的做法：用一个额外的 boolean[][] visited 记录已访问格子。

class Solution {
    private char[][] board;
    private String word;
    private boolean[][] visited;
    private int rows, cols;
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        rows = board.length;
        cols = board[0].length;
        visited = new boolean[rows][cols];

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, 0)) return true; // 每个格子都可能作为起点
            }
        }
        return false;
    }

    private boolean dfs(int r, int c, int idx) {
        if (idx == word.length()) return true; // 所有字母匹配完成
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || visited[r][c] || board[r][c] != word.charAt(idx)) {
            return false;
        }

        visited[r][c] = true; // 标记已访问
        for (int[] d : dirs) {
            if (dfs(r + d[0], c + d[1], idx + 1)) return true;
        }
        visited[r][c] = false; // 回溯：恢复
        return false;
    }
}

复杂度（逐步推导）：起点有 m × n 个。每个起点的 DFS 第一步 4 个方向，之后每步最多 3 个方向（不能回头），深度最多 L（L = word.length()），所以上界 O(m × n × 4^L)（更紧的界是 3^L，但通常记 4^L）。空间：visited 数组 O(m × n)，递归栈 O(L)，合计 O(m × n)。

瓶颈：额外维护一个 m × n 的 visited 二维数组，空间开销 O(m × n)。

解法二：优化 / 最优（原地标记，省 visited）

把已访问格子在 board 里原地改成无效字符 '#'，回溯时恢复，省掉 visited 数组。

class Solution {
    private char[][] board;
    private String   word;
    private int rows, cols;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word  = word;
        rows = board.length;
        cols = board[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int r, int c, int idx) {
        if (idx == word.length()) return true; // 所有字母匹配完成

        // 越界、已访问（'#'）或字母不匹配
        if (r < 0 || r >= rows || c < 0 || c >= cols
                || board[r][c] == '#' || board[r][c] != word.charAt(idx)) {
            return false;
        }

        char tmp = board[r][c];
        board[r][c] = '#'; // 原地标记为已访问

        boolean found = dfs(r - 1, c, idx + 1)
                     || dfs(r + 1, c, idx + 1)
                     || dfs(r, c - 1, idx + 1)
                     || dfs(r, c + 1, idx + 1);

        board[r][c] = tmp; // 回溯：恢复格子

        return found;
    }
}

复杂度（逐步推导）：时间同上，起点 m × n 个、每步最多 4 方向、深度 L，上界 O(m × n × 4^L)。空间：省掉了 visited 数组，只剩递归栈深度 O(L)。

多解法对比

解法时间空间适用场景
DFS + visited 数组O(m × n × 4^L)O(m × n)更直观，不允许改入参时用
原地标记O(m × n × 4^L)O(L)空间更优，面试标准解

本题约束下 m, n ≤ 6，word.length ≤ 15，两种都能过。手撕推荐原地标记，省空间且展示你对「回溯恢复现场」的理解。

CodeTop 变体

131. 分割回文串

题意

给你字符串 s，将 s 分割成若干子串，使每个子串都是回文串。返回所有可能的分割方案。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

题目本质：回溯 + 回文判断剪枝——每次从当前位置 start 往后枚举分割点 end，若 [start, end] 是回文则加入路径，递归处理 end + 1 开始的部分，否则跳过（剪枝）。

现实类比：切蛋糕。从左到右尝试每个切割点，每段必须是回文（镜像对称），不满足就不切，满足就切下来继续处理剩余部分。

难点与易错点

  1. 分割点枚举与下标：切出的子串是 s[start, end]（闭区间），递归从 end + 1 继续。容易把 end 的边界写成 end <= s.length() 或 substring 的结束下标写成 end（应该 end + 1）。
  2. 回文判断剪枝：只有当 [start, end] 是回文时才递归，否则直接跳过——这是「剪枝」所在，能砍掉大量无效分割路径。
  3. 双指针判断细节：isPalindrome 用 l < r 比较，奇数长度中心字符不用比；注意 substring(start, end + 1) 才是闭区间对应的子串。

解法一：暴力 / 直观（回溯 + 双指针现场判断）

每次切分都用双指针现场判断子串是否回文。

class Solution {
    private List<List<String>> result = new ArrayList<>();
    private List<String>       path   = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return result;
    }

    private void backtrack(String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path)); // 整个 s 已分割完
            return;
        }

        for (int end = start; end < s.length(); end++) {
            // 只有当 [start, end] 是回文时，才继续向下递归
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1);
                path.remove(path.size() - 1); // 回溯
            }
        }
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) return false;
        }
        return true;
    }
}

复杂度（逐步推导）：最坏情况 s 全是相同字符（如 "aaaa"），每个切点都可切可不切，切法数 2^(n-1)；每个方案收集时 substring 和拷贝路径共 O(n)，所以时间 O(n × 2^n)。空间：递归深度 O(n)。

瓶颈：回文判断每次都用双指针扫一遍子串，最坏 O(n)；在需要反复判断回文的场景（尤其变体 132 题）下，这是主要开销。

解法二：优化 / 最优（DP 预处理回文表）

用 DP 提前算好 dp[i][j]（s[i..j] 是否回文），回溯时回文判断降到 O(1)。

class Solution {
    private boolean[][] dp; // dp[i][j] 表示 s[i..j] 是否回文
    private List<List<String>> result = new ArrayList<>();
    private List<String>       path   = new ArrayList<>();

    public List<List<String>> partition(String s) {
        int n = s.length();
        dp = new boolean[n][n];
        // DP 预处理所有子串是否回文（区间 DP，按长度从小到大）
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                // 两端相等，且中间是回文（长度为 0 或 1 时天然成立）
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
        backtrack(s, 0);
        return result;
    }

    private void backtrack(String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (dp[start][end]) { // O(1) 判断回文
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1);
                path.remove(path.size() - 1);
            }
        }
    }
}

复杂度（逐步推导）：DP 预处理两层循环，O(n^2)；回溯部分每个方案收集时 substring 拷贝 O(n)，切法数最坏 2^(n-1)，时间 O(n × 2^n)。总时间 O(n^2 + n × 2^n)，主项仍是 O(n × 2^n)。空间：DP 表 O(n^2)，递归栈 O(n)，合计 O(n^2)。

说明：本题 n ≤ 16，双指针判断的开销并不大，DP 优化的收益有限；DP 的真正价值体现在变体 132 题（求最少分割次数），那里必须用回文 DP 表。这里写出来是为了展示「用空间换时间」的优化思路，面试时点到即可。

多解法对比

解法时间空间适用场景
回溯 + 双指针判断O(n × 2^n)O(n)本题标准解，简单直接
DP 预处理 + 回溯O(n × 2^n)O(n^2)需要频繁回文判断 / 变体 132 的铺垫

本题约束下 n ≤ 16，双指针法即可。手撕先写双指针法（最直观），再提 DP 预处理作为「如果回文判断变多」的优化，展示广度。

CodeTop 变体

51. N 皇后

题意

将 n 个皇后放在 n x n 棋盘上，使皇后互不攻击（任意两个不同行、不同列、不同对角线）。返回所有不同解的棋盘布局。

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

题目本质：逐行回溯 + 三个约束集合剪枝——每行放一个皇后，列和两条对角线不冲突时才放，用 HashSet 记录已占用的列和对角线（行-列 / 行+列），O(1) 检查冲突。

现实类比：象棋摆局。每一横排放一枚皇后，已占用的纵列和两条斜线记录在「禁区表」里，新皇后落点不在禁区才可以放。

难点与易错点

  1. 对角线编码：这是题眼。同一条主对角线（左上→右下）上所有格子的 row - col 恒定，同一条副对角线（右上→左下）上所有格子的 row + col 恒定。用这两个值做 HashSet 的 key，就能 O(1) 判断对角线冲突。
  2. 三个集合都要撤销：cols、diag1、diag2 三个集合，放皇后时都 add，回溯时都要 remove，漏掉任何一个 remove，后续行就会误判冲突而漏解。
  3. buildBoard 复用陷阱：每行都要 new char[n] 再 Arrays.fill('.')，不能复用一个 char[]（否则所有行引用同一个数组，互相覆盖）。

解法一：暴力 / 直观（逐列扫描检查冲突）

每放一个皇后，都遍历「前面已经放好的皇后」，逐个检查是否同列 / 同对角线。

class Solution {
    private List<List<String>> result = new ArrayList<>();
    private int[] queens; // queens[row] = col，记录每行皇后所在列
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        queens = new int[n];
        Arrays.fill(queens, -1);
        backtrack(0);
        return result;
    }

    private void backtrack(int row) {
        if (row == n) {
            result.add(buildBoard()); // 所有行放置完毕
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                queens[row] = col;
                backtrack(row + 1);
                queens[row] = -1; // 回溯
            }
        }
    }

    // 检查 (row, col) 是否与前面已放皇后冲突：O(n)
    private boolean isValid(int row, int col) {
        for (int r = 0; r < row; r++) {
            int c = queens[r];
            if (c == col) return false;                          // 同列
            if (Math.abs(row - r) == Math.abs(col - c)) return false; // 同对角线
        }
        return true;
    }

    private List<String> buildBoard() {
        List<String> board = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            char[] row = new char[n]; // 每行都要新数组
            Arrays.fill(row, '.');
            row[queens[r]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

复杂度（逐步推导）：递归树节点数小于 n!（第 k 行最多 n - k + 1 种列可选，逐行递减），上界 O(n!)。每个节点 isValid 要扫前面 O(n) 个皇后，所以时间 O(n × n!)。空间：queens 数组 O(n)，递归栈 O(n)，合计 O(n)。

瓶颈：每次 isValid 都要 O(n) 扫描前面已放的皇后，检查冲突的开销随行数增长，常数偏大。

解法二：优化 / 最优（三个 HashSet O(1) 判冲突）

用三个集合分别记录已占用的列、主对角线（row - col）、副对角线（row + col），检查冲突降到 O(1)。

class Solution {
    private List<List<String>> result  = new ArrayList<>();
    private Set<Integer>       cols    = new HashSet<>(); // 已占用的列
    private Set<Integer>       diag1   = new HashSet<>(); // row - col（主对角线）
    private Set<Integer>       diag2   = new HashSet<>(); // row + col（副对角线）
    private int[]              queens;                   // 每行皇后所在列
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n  = n;
        queens  = new int[n];
        Arrays.fill(queens, -1);
        backtrack(0);
        return result;
    }

    private void backtrack(int row) {
        if (row == n) {
            result.add(buildBoard()); // 所有行放置完毕，生成棋盘
            return;
        }

        for (int col = 0; col < n; col++) {
            // 当前列或两条对角线有冲突，跳过（O(1) 判断）
            if (cols.contains(col) || diag1.contains(row - col)
                    || diag2.contains(row + col)) continue;

            // 放置皇后：更新约束集合
            queens[row] = col;
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);

            backtrack(row + 1);

            // 撤销皇后：回溯
            queens[row] = -1;
            cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }

    // 根据 queens 数组生成棋盘字符串列表
    private List<String> buildBoard() {
        List<String> board = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[r]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}

复杂度（逐步推导）：递归树节点数上界仍是 O(n!)（实际解数量渐近约 n! / e，常数更小）。每个节点用 HashSet 做 O(1) 冲突检查；每个解生成棋盘 O(n^2)。总时间 O(n!)（主项），空间三个 HashSet + queens 数组，O(n)。

对比：解法一每个节点 O(n) 判冲突，解法二 O(1)，把时间从 O(n × n!) 压到 O(n!)，这是「用 O(1) 的集合查询替代 O(n) 的线性扫描」的典型优化。

💭 思考：N 皇后最难的一步——对角线冲突怎么 O(1) 判？——先看暴力版：每放一个皇后都要回头扫前面所有皇后，逐个比对「同列 / 行差 == 列差」判断对角线，O(n) 一次。突破口是给对角线「编码」：同一条主对角线（左上→右下）上所有格子的 row - col 恒定，副对角线（右上→左下）上 row + col 恒定。于是用两个 HashSet 分别存 row - col 和 row + col，冲突判断就从「线性扫描」变成「集合 contains」。看到「棋盘上判斜线冲突」这个信号，就想「找一条对角线的公共不变量」——row±col 是这条题的题眼，其余部分都是标准回溯骨架。

多解法对比

解法时间空间适用场景
逐列扫描判冲突O(n × n!)O(n)最直观，容易讲清对角线冲突
三个 HashSet O(1) 判冲突O(n!)O(n)面试标准解，对角线编码是加分点

本题约束 n ≤ 9，两种都能过，但 HashSet 法常数更小。手撕推荐 HashSet 法，并把「row - col / row + col 编码对角线」讲清楚，这是 N 皇后的核心考点。

CodeTop 变体

小结

把 8 道回溯题串起来，其实只有一条主线：

面试手撕时，先把模板的「选择 → 递归 → 撤销」写稳，再回答两个必被追问的问题：「为什么这里要撤销」（不同分支共享同一状态，不撤销会污染后续分支）和**「剪枝砍掉了什么」**（砍掉注定失败的分支，把复杂度从全量穷举降下来）。这两点答清楚，回溯题就稳了。

章末提问

  1. 什么时候用回溯、什么时候用 DP？ —— 结论先行：求「所有解/所有方案」用回溯，求「最优值/方案数」用 DP。因为回溯的本质是在递归树上穷举每一种选择并收集所有合法路径，DP 则是缓存重叠子问题后取最优；所以组合总和 IV（求方案数、顺序敏感）用回溯会超时，必须换 DP。

  2. 子集/组合类题怎么去重？ —— 结论先行：靠「只往后选」的 index 保证顺序，循环从 index 开始、递归传 i（可重复）或 i+1（不可重复）。因为组合不区分顺序，[1,2] 和 [2,1] 应视为同一个，强制每个位置只选它后面的元素就天然去重；含重复元素时再排序 + 同层去重 continue。

  3. 为什么收集结果时一定要拷贝 new ArrayList<>(path)？ —— 结论先行：因为 path 是全局共享、会被回溯不断改写的引用。直接 add(path) 会让所有已收集的结果都指向同一个最终为空的列表；拷贝一份快照才能冻结当时的路径内容。

  4. 回溯的复杂度怎么推？ —— 结论先行：复杂度 = 递归树的节点数（或叶子数）× 每个节点的代价。因为排列有 n! 个叶子、子集有 2^n 个节点、组合总和约 n^(T/min)、括号生成是卡特兰数 4^n/√n，每个节点/叶子再乘上收集时的拷贝 O(n)，就得到 O(n×n!)、O(n×2^n) 等。

  5. N 皇后两条对角线怎么编码到集合里？ —— 结论先行：用 row - col 标记主对角线、row + col 标记副对角线。因为同一主对角线上所有格子的 row-col 恒定、副对角线上 row+col 恒定，用这两个值做 key 就能 O(1) 判冲突，把逐列扫描的 O(n) 压到 O(1)。

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——二分查找篇（边界控制与旋转数组）
Next Post
LeetCode Hot 100——图论篇（DFS、BFS、拓扑排序、Trie）