回溯 · 排列、组合与剪枝

从 LC 46 出发，看回溯框架的"选 → 递归 → 撤销"三段式，以及组合 / 排列的剪枝边界。

Medium预计阅读 45 分钟更新于 2026-05-23

1. 核心原理

回溯（backtracking）要解决的问题模板长这样："给你一个集合 / 棋盘 / 状态空间，列出所有满足条件的决策序列"——排列、组合、子集、N 皇后、数独、迷宫路径、表达式划分，骨架都是同一套。它和"求一个最优值"的 DP / 贪心明显不一样：回溯一定要把每条合法路径都吐出来，少一条都算错。

暴力枚举为什么不行？

最直觉的写法是先生成所有候选、再过滤。例如全排列就枚举所有 n! 种顺序、子集就枚举 2^n 个 (mask, subset) 对。问题有两个：一是组合 / 排列 / 子集的"候选总数公式"各不相同，没法用统一的 for 循环写出来；二是哪怕生成出来，带约束的题（N 皇后、组合总和、数独）还要逐个验证，复杂度雪上加霜。

回溯为什么干净？

关键洞察：把"做决策的过程"画成决策树，每一层枚举"这一步选谁"，从根走到叶就是一条候选答案。走的过程中维护一份共享状态（path / used / cols），进入分支前修改、退出分支后撤销——边走边剪。

                    根 []
        /            |            \
      选 1         选 2          选 3
     /   \         /   \         /   \
   选 2  选 3    选 1  选 3    选 1  选 2     <- 已用过的不再选
    |     |       |     |       |     |
  [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

每个叶子对应一个完整答案，每条边对应一次"选 → 递归 → 撤销"。剪枝就是在决策树上提前砍掉不可能产生合法叶子的子树。

模板三段式

回溯骨架固定为三步，§2 给完整模板代码：

选：把当前候选纳入状态（path.append(x) / used[i] = True）
递归：进入下一层决策
撤销：把状态恢复到选之前（path.pop() / used[i] = False）

顺序固定：先选，再递归，最后撤销。少撤销一步，下一次循环就会用到错的状态。

2. 通用模板

回溯三段式的最小骨架，把"决策树深度 + 当前层候选 + 终止条件"三件事抽出来，剩下的题目逻辑往里填：

def backtrack(nums):
    n = len(nums)
    ans, path, used = [], [], [False] * n

    def dfs():
        if len(path) == n:                 # 1. 终止条件
            ans.append(path[:])            #    复制快照
            return
        for i in range(n):                 # 2. 枚举当前层候选
            if used[i]:
                continue                   #    （可选）剪枝
            used[i] = True                 #    选
            path.append(nums[i])
            dfs()                          #    递归
            path.pop()                     #    撤销
            used[i] = False

    dfs()
    return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int[] nums;
    private boolean[] used;

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

    private void dfs() {
        if (path.size() == nums.length) {            // 1. 终止条件
            ans.add(new ArrayList<>(path));          //    复制快照
            return;
        }
        for (int i = 0; i < nums.length; i++) {      // 2. 枚举候选
            if (used[i]) continue;                   //    剪枝
            used[i] = true;                          //    选
            path.add(nums[i]);
            dfs();                                   //    递归
            path.remove(path.size() - 1);            //    撤销
            used[i] = false;
        }
    }
}

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> nums_;
    vector<bool> used;

    void dfs() {
        if (path.size() == nums_.size()) {           // 1. 终止条件
            ans.push_back(path);                     //    vector 拷贝构造
            return;
        }
        for (int i = 0; i < (int)nums_.size(); i++) {// 2. 枚举候选
            if (used[i]) continue;                   //    剪枝
            used[i] = true;                          //    选
            path.push_back(nums_[i]);
            dfs();                                   //    递归
            path.pop_back();                         //    撤销
            used[i] = false;
        }
    }

public:
    vector<vector<int>> backtrack(vector<int>& nums) {
        nums_ = nums;
        used.assign(nums.size(), false);
        dfs();
        return ans;
    }
};

两点要说明：

path 传引用还是拷贝：Python / Java / C++ 三种语言里 path 都是同一个对象贯穿全程（引用 / 引用 / 成员变量），所以收答案时必须复制一份快照（path[:] / new ArrayList<>(path) / vector 隐式拷贝构造）。直接 push 引用会让 ans 里所有元素最终指向同一个空 list。
used 用 boolean[] 还是 set：固定下标范围（如 [0, n)）用数组，O(1) 且常数比 HashSet 小一截；下标稀疏或是字符串（N 皇后的对角线、数独的九宫格）才上 set。
什么时候要剪枝：朴素回溯就一条 if used[i]: continue；带约束的题需要在循环里再加 if 不合法: continue 或 if 不可能合法: break（详见 §4 三类剪枝）。

3. 母题精讲

LeetCode 46. Permutations

链接：LeetCode 46

题目（中文翻译）：给一个不含重复数字的整数数组 nums，返回它所有可能的全排列。可以按任意顺序返回。

数据范围：

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
所有数字互不相同

示例：

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

朴素思路：能不能直接枚举？

最直觉的写法：枚举所有 n! 种顺序。怎么枚举？

一种是先把数组排序，然后调标准库 next_permutation （C++）或者手写一个；另一种是写三重 / 四重 / n 重循环——但 n 是变量，没法这么写死。

第三种是"先随便造一堆候选、再去重"：把 nums 重复 n 次拼成长度 n² 的数组，再从中挑长度 n 的子序列。这复杂度爆炸到 O(n^n · n) 还得 dedup，工程上是 dirty hack。

回溯解法

把"决定第 1 位放谁、第 2 位放谁……第 n 位放谁"看成一棵决策树，逐层往下走，走到底就得到一个排列。走的过程中维护一个 used 数组，记录哪些数字已经被用过；走到底时把当前路径加到答案里；回退时把 used 标记清掉。

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        ans = []
        path = []
        used = [False] * n

        def dfs():
            if len(path) == n:
                ans.append(path[:])                  # 走到叶子，复制一份
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True                       # 选
                path.append(nums[i])
                dfs()                                # 递归
                path.pop()                           # 撤销
                used[i] = False

        dfs()
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int[] nums;
    private boolean[] used;

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

    private void dfs() {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));          // 走到叶子，复制一份
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;                          // 选
            path.add(nums[i]);
            dfs();                                   // 递归
            path.remove(path.size() - 1);            // 撤销
            used[i] = false;
        }
    }
}

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> nums_;
    vector<bool> used;

    void dfs() {
        if (path.size() == nums_.size()) {
            ans.push_back(path);                     // 走到叶子，拷贝构造
            return;
        }
        for (int i = 0; i < (int)nums_.size(); i++) {
            if (used[i]) continue;
            used[i] = true;                          // 选
            path.push_back(nums_[i]);
            dfs();                                   // 递归
            path.pop_back();                         // 撤销
            used[i] = false;
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        nums_ = nums;
        used.assign(nums.size(), false);
        dfs();
        return ans;
    }
};

复杂度：时间 O(n! · n)——共 n! 个排列，每个 O(n) 复制；空间 O(n) 递归栈 + O(n) 标记，输出空间不计。

这份代码就是回溯的"标准模板"。三件事值得拆开看：

第一，决策树。dfs() 每一次进入对应决策树的一个节点，节点里的 for i in range(n) 枚举所有"还能选的孩子"。决策树深度恰好是 n，叶子数恰好是 n!。

第二，选 / 递归 / 撤销。这是回溯的核心三步：进入分支前把状态改掉（used[i] = True / path.append），递归走完再把状态恢复（used[i] = False / path.pop）。如果只改不撤销，下一次循环就用到错的状态了。

第三，为什么要复制 path[:]？因为 path 是同一个 list 对象，递归全程在原地改。如果直接 ans.append(path)，最后所有元素都指向那个最终被清空的 list。复制一份才能保住快照。

下面把"选 / 递归 / 撤销"抽象成一套可以套到组合 / 子集 / N 皇后的通用框架。

4. 抽象：回溯三段式 + 剪枝

回溯（backtracking）是 DFS 的一种特化——在搜索过程中"选了 → 走下去 → 不行就退回来 / 走完就退回来"。它适合的题型有两个共同特征：

答案是一个集合 / 序列（不是单个数值），且需要把所有满足条件的都列出来
每一步有有限多个候选，可以一个一个试

4.1 三段式骨架

def dfs(state):
    if 到达终止条件:
        记录答案
        return
    for choice in 当前可选项:
        做选择（修改 state）
        dfs(下一层 state)
        撤销选择（恢复 state）

三件套：做选择、递归、撤销选择。其中"撤销"是相对"修改"对称的——加进去就 pop 出来，标记成 True 就改回 False，染色了就涂回原色。

4.2 决策树的两种走法：排列 vs 组合

排列和组合在决策树上长得完全不同。

排列：每一层都从全部 n 个候选里挑一个还没用过的。需要一个 used 数组（或 set）来标记。决策树有 n! 个叶子。

              []
       /      |      \
      1       2       3        <- 第 1 层：从 {1,2,3} 任选
     / \     / \     / \
    12  13  21 23   31 32      <- 第 2 层：从剩下 2 个里选
    |   |   |  |    |  |
   123 132 213 231 312 321     <- 第 3 层：只剩 1 个

组合：选过的位置后面不再考虑，用一个 start 指针标记"下一次从哪里开始"。决策树有 C(n, k) 个叶子。

              []
       /      |      \
      1       2       3        <- 第 1 层
     / \      |
    2   3     3                <- 第 2 层：start=i+1
    |   
    3                          <- 第 3 层

关键区别：

类型	状态	候选范围	叶子数
排列	`used[]`	`for i in range(n)` 跳过 `used[i]`	`n!`
组合	`start` 指针	`for i in range(start, n)`	`C(n, k)`
子集	`start` 指针	同组合，但所有节点都收	`2^n`

记住一句话："顺序敏感用 used，顺序无关用 start"。[1, 2] 和 [2, 1] 在排列里是两个答案，在组合里是同一个——这就是用 start 指针避免重复的本质。

4.3 三种常见剪枝

回溯天然指数级，跑不动的题靠剪枝。三种最常见：

可行性剪枝（目标剪枝）：当前状态已经不可能产生合法答案，立刻 return。LC 39 里 target < 0 就停——后面只会越加越大。
长度剪枝（结构剪枝）：LC 77 求 C(n, k) 时，循环上界改成 n - (k - len(path)) + 2，剩下不够 k 个的死分支根本不进。
同层去重：数组有重复元素时，先 sort，再加一行 if i > start and nums[i] == nums[i - 1]: continue。注意是 i > start 不是 i > 0——下一章 LC 47 / 40 / 90 会反复用。

回溯题写成"叶子数 × 单次复制 / 验证开销"：LC 46 是 O(n! · n)、LC 77 是 O(C(n,k) · k)、LC 39 上界 O(2^target)、LC 78 是 O(2^n · n)、LC 51 是 O(n! · n²)。回溯不是多项式，但靠剪枝把"实际跑过的节点数"压到能接受。LC 数据范围给的 n ≤ 6 / n ≤ 9 就是为了限制最坏情况。

5. 例题（三道）

按"决策树形状递增"排：排列 → 组合 → 组合 + 剪枝。

5.1 LC 46 全排列

回到本章开头那道题，重点看 used 数组版和交换法的对照——used 版就是 §3 给的那份代码（包成 class Solution 即可提交），复杂度 O(n! · n)、空间 O(n)。下面给交换法对比，三语言 Tab：

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        ans = []
        def dfs(first):
            if first == len(nums):
                ans.append(nums[:])
                return
            for i in range(first, len(nums)):
                nums[first], nums[i] = nums[i], nums[first]
                dfs(first + 1)
                nums[first], nums[i] = nums[i], nums[first]
        dfs(0)
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private int[] nums;

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ans;
    }

    private void dfs(int first) {
        if (first == nums.length) {
            // 拷贝整段，否则后续交换会污染 ans
            List<Integer> snap = new ArrayList<>(nums.length);
            for (int v : nums) snap.add(v);
            ans.add(snap);
            return;
        }
        for (int i = first; i < nums.length; i++) {
            swap(first, i);
            dfs(first + 1);
            swap(first, i);   // 撤销
        }
    }

    private void swap(int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

class Solution {
    vector<vector<int>> ans;
    vector<int> nums_;

    void dfs(int first) {
        if (first == (int)nums_.size()) {
            ans.push_back(nums_);  // vector 拷贝构造
            return;
        }
        for (int i = first; i < (int)nums_.size(); i++) {
            swap(nums_[first], nums_[i]);
            dfs(first + 1);
            swap(nums_[first], nums_[i]);  // 撤销
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        nums_ = nums;
        dfs(0);
        return ans;
    }
};

两种实现的决策树完全不同：

used 版决策树：每一层都从 0..n-1 里挑没标记的，按"原数组顺序"展开。
交换法决策树：第 0 层固定 nums[0..n-1] 各换一次到首位，第 1 层在 nums[1..n-1] 各换一次到 nums[1]，依此类推。

输出的排列集合一样，但内部顺序不一样。面试里被问 follow-up "怎么减空间"时，交换法是答案；被问"怎么处理重复"时（LC 47），used 版更顺。

几个易错点：

path[:] 别忘——直接 ans.append(path) 是 Python 经典坑。
终止条件 len(path) == n 写起来比 len(path) == len(nums) 短，两者都是 O(1)。
Java / C++ 用 new ArrayList<>(path) / vector<int>(path) 做拷贝。

Follow-up：如果题目改成"求所有不同长度的组合"或者"求所有长度为 k 的组合"——[1, 2, 3] 选 2 个，结果是 [[1,2], [1,3], [2,3]]，不要 [[2, 1]]（因为 [1, 2] 和 [2, 1] 算同一个组合）？

5.2 LC 77 组合

链接：LeetCode 77

题意：给两个整数 n 和 k，返回 [1, n] 中所有可能的 k 个数的组合。可以按任何顺序返回。

数据范围：

1 ≤ n ≤ 20
1 ≤ k ≤ n

示例：

输入：n = 4, k = 2
输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
解释：注意没有 [2, 1]，因为组合无序。

组合和排列的唯一区别：组合无序。[1, 2] 和 [2, 1] 是同一个，只保留一种。

直接套排列模板再去重？太蠢。正确做法是用 start 指针强制每次只往后选。

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        ans, path = [], []

        def dfs(start):
            if len(path) == k:
                ans.append(path[:])
                return
            for i in range(start, n + 1):
                path.append(i)
                dfs(i + 1)                           # 下一层从 i+1 开始，不回头
                path.pop()

        dfs(1)
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int n, k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        dfs(1);
        return ans;
    }

    private void dfs(int start) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            dfs(i + 1);                              // 下一层从 i+1 开始，不回头
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    int n_, k_;

    void dfs(int start) {
        if ((int)path.size() == k_) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i <= n_; i++) {
            path.push_back(i);
            dfs(i + 1);                              // 下一层从 i+1 开始，不回头
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        n_ = n;
        k_ = k;
        dfs(1);
        return ans;
    }
};

复杂度 O(C(n, k) · k)——共 C(n, k) 个组合，每个 O(k) 复制。

为什么 start 指针就能避免重复？

决策树上看：第 1 层选 1，第 2 层 start = 2，只能在 {2, 3, 4} 里选；选 2，第 2 层 start = 3，只能在 {3, 4} 里选。所以 [1, 2] 和 [2, 1] 不会同时出现——[2, 1] 这条路径根本不存在，因为选 2 之后 start = 3，回不到 1。

简单决策树（n = 4, k = 2）：

                    []
        /      |       |       \
       1       2       3        4
     / | \   / |       |
    2  3  4 3  4       4

每个叶子都是一个长度 2 的组合，按字典序自然排列。

加上长度剪枝：循环上界从 n + 1 改成 n - (k - len(path)) + 2——如果剩下元素已经凑不够 k - len(path) 个，直接 break。例如 n = 5, k = 3 且 path = [] 时，i 最多到 3（i = 4 时只剩 {4, 5} 凑不够 3 个）。这一剪实测能从几十毫秒降到几毫秒。

Follow-up：如果数字可以重复使用呢？比如 [2, 3, 5]，要凑出和为 8 的所有组合：[2, 2, 2, 2]、[2, 3, 3]、[3, 5]。同一个数字想用几次用几次——这跟 LC 77 的 start + 1 不一样了，因为 i 自己也能再选。

5.3 LC 39 组合总和

链接：LeetCode 39

题意：给一个无重复的正整数数组 candidates 和目标整数 target。找出 candidates 中所有可以使数字和为 target 的唯一组合。同一个数字可以无限制重复被选取。组合无序，[2, 2, 3] 和 [3, 2, 2] 算同一个，只输出一次。

数据范围：

1 ≤ candidates.length ≤ 30
2 ≤ candidates[i] ≤ 40
1 ≤ target ≤ 40
所有元素互不相同

示例：

输入：candidates = [2, 3, 6, 7], target = 7
输出：[[2,2,3], [7]]
解释：2+2+3 = 7，7 = 7。其他组合（比如 2+5）凑不出 7 因为没有 5。

这道题在 LC 77 的"组合 + start 指针"基础上加了两件事：

同一个数字可以重复用 → 递归调用时 dfs(i) 而不是 dfs(i + 1)，让下一层还能选自己。
目标剪枝 → target < 0 时直接返回，省指数级开销。

class Solution:
    def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()                            # 排序后剪枝更紧
        ans, path = [], []
        n = len(candidates)

        def dfs(start, remain):
            if remain == 0:
                ans.append(path[:])
                return
            for i in range(start, n):
                if candidates[i] > remain:           # 排序后这条剪枝直接 break
                    break
                path.append(candidates[i])
                dfs(i, remain - candidates[i])       # 注意是 i 不是 i + 1
                path.pop()

        dfs(0, target)
        return ans

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    private int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);                     // 排序后剪枝更紧
        this.candidates = candidates;
        dfs(0, target);
        return ans;
    }

    private void dfs(int start, int remain) {
        if (remain == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) break;       // 排序后这条剪枝直接 break
            path.add(candidates[i]);
            dfs(i, remain - candidates[i]);          // 注意是 i 不是 i + 1
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> cand;

    void dfs(int start, int remain) {
        if (remain == 0) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i < (int)cand.size(); i++) {
            if (cand[i] > remain) break;             // 排序后这条剪枝直接 break
            path.push_back(cand[i]);
            dfs(i, remain - cand[i]);                // 注意是 i 不是 i + 1
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); // 排序后剪枝更紧
        cand = candidates;
        dfs(0, target);
        return ans;
    }
};

复杂度上界 O(2^target)——实际剪枝后远小于此。

三个关键点细看：

第一，dfs(i, ...) vs dfs(i + 1, ...)

LC 77：dfs(i + 1) 因为每个数只能用一次。
LC 39：dfs(i) 因为同一个数可以用多次。

但要注意是 dfs(i, ...) 不是 dfs(start, ...)——后者会让下一层重新从 start 开始，等价于"可以回头选小的"，会产生 [3, 2] 这种乱序组合（跟 [2, 3] 重复）。dfs(i, ...) 才能在"允许重复"的同时保持"非递减顺序"。

第二，排序 + break 剪枝

排序后 candidates[i] > remain 时，因为后面只会更大，可以直接 break 整个循环。如果不排序，得用 continue，效率差很多。

举例 candidates = [2, 3, 6, 7], target = 7：当 path = [2, 2]、remain = 3 时，i 从 1 开始（前一次选 i = 1 是 3）扫到 i = 1 选 3，remain = 0 加入答案；然后 i = 2 是 6 > 3，break。省掉了 i = 3 是 7 的死路。

第三，传 remain 还是传 target？

两种写法都行：

传 remain：每次递减，递归参数变化，函数无状态。推荐。
传 target 不变，在函数里维护 sum(path)：每次 O(k) 求和，慢；或维护一个全局 cur_sum，递归前 +=、递归后 -=，可以但容易忘。

传 remain 是函数式风格，调试也方便——打印一下立刻知道还差多少。

Follow-up：如果 candidates 里有重复元素（比如 [2, 2, 3]）且每个元素只能用一次呢？这就是 LC 40 组合总和 II，藏着"同层去重"的经典模式——下一节 paywall 区会详细讲。

6. 边界、易错与复杂度

6.1 撤销忘了：经典坑

每个 path.append 必须对应一个 path.pop，每个 used[i] = True 必须对应 used[i] = False。漏一个，下一次循环就用到错的状态。调试技巧：把"做选择"和"撤销选择"按相反顺序上下对齐写——肉眼就能扫到漏掉的那条。

6.2 `path[:]` 还是 `path`：引用坑

ans.append(path)        # 错：所有元素指向同一个 list，最后会被清空
ans.append(path[:])     # 对：复制一份
ans.append(list(path))  # 对：同上

ans.add(path);                       // 错：所有元素指向同一个 ArrayList
ans.add(new ArrayList<>(path));      // 对：复制一份
ans.add(List.copyOf(path));          // 对：不可变快照

ans.push_back(path);             // 对：vector 默认是拷贝构造，新对象
ans.push_back(std::move(path));  // 错：path 被移走，后面 pop_back 会未定义
// 想避免拷贝？必须确保 path 之后不再被用——回溯里基本不可能

Java / C++ 行为反过来：Java ans.add(path) 加的是同一个 list 引用（和 Python 一样的坑），必须 new ArrayList<>(path)；C++ 的 push_back 默认拷贝构造，不需要手动复制，但别 std::move，否则后续 pop_back 会作用到已被搬空的对象上。

6.3 `i > start` 不是 `i > 0`：同层去重的边界

排序后跳过同层重复兄弟 if i > start and nums[i] == nums[i - 1]: continue。

为什么是 i > start 不是 i > 0？举例 nums = [1, 1, 2] 求 C(3, 2)：第一层 start = 0、i = 0 选第一个 1，path = [1]。第二层 start = 1、i = 1 选第二个 1，path = [1, 1]——这是合法的，两个 1 在不同层。如果写 i > 0，第二层 i = 1 > 0 且 nums[1] == nums[0] 就 skip 了，[1, 1] 被错杀。

正确判断："当前层之内是否出现了相同值"——i > start 表示不是这一层的第一个。

6.4 排列去重的两种写法（LC 47 预习）

排列没有 start，去重要看 used。两种主流写法都对——not used[i - 1]（前邻未用）vs used[i - 1]（前邻已用）。前者剪得更早、跑得更快（在决策树更高层就剪），推荐 not used[i - 1]：相同值要"从前到后依次使用"，前一个还没用就别用后一个。

6.5 复杂度速查

题	时间	空间（不含输出）
LC 46 全排列	`O(n! · n)`	`O(n)`
LC 77 组合	`O(C(n,k) · k)`	`O(k)`
LC 39 组合总和	上界 `O(2^target)`，剪枝后远低	`O(target / min)`

回溯题的精确复杂度往往写不出来，因为依赖剪枝效果。面试讲清"O(候选树叶子数 × 单次复制)"加上"实际靠剪枝"就够了。

6.6 回溯不是孤岛：与记忆化 / DP / 状压 DP 的边界

回溯解的是"穷举所有路径"问题。当题目只关心叶子的数值答案而非路径本身时，回溯往往可以平滑过渡到记忆化 / DP / 状压 DP。三条桥写在下面：

桥 1：回溯 → 记忆化搜索

只要 dfs(state) 的返回值只依赖于 state、不依赖如何到达 state（即无后效性），就能在递归签名上加 @functools.cache，让重复状态只算一次。

# LC 139 Word Break: 回溯枚举所有切分 → @cache 后退化为记忆化
@cache
def dfs(i: int) -> bool:
    if i == len(s):
        return True
    return any(s.startswith(w, i) and dfs(i + len(w)) for w in word_set)

// LC 139 Word Break: 回溯 + memo 数组
private String s;
private Set<String> wordSet;
private Boolean[] memo;

public boolean wordBreak(String s, List<String> wordDict) {
    this.s = s;
    this.wordSet = new HashSet<>(wordDict);
    this.memo = new Boolean[s.length()];
    return dfs(0);
}

private boolean dfs(int i) {
    if (i == s.length()) return true;
    if (memo[i] != null) return memo[i];
    for (String w : wordSet) {
        if (s.startsWith(w, i) && dfs(i + w.length())) {
            return memo[i] = true;
        }
    }
    return memo[i] = false;
}

// LC 139 Word Break: 回溯 + memo 数组（-1 未算，0 false，1 true）
class Solution {
    string s;
    unordered_set<string> wordSet;
    vector<int> memo;

    bool dfs(int i) {
        if (i == (int)s.size()) return true;
        if (memo[i] != -1) return memo[i];
        for (const auto& w : wordSet) {
            if (s.compare(i, w.size(), w) == 0 && dfs(i + w.size())) {
                return memo[i] = 1;
            }
        }
        return memo[i] = 0;
    }

public:
    bool wordBreak(string s, vector<string>& wordDict) {
        this->s = s;
        wordSet = {wordDict.begin(), wordDict.end()};
        memo.assign(s.size(), -1);
        return dfs(0);
    }
};

判别条件：递归签名里只有"决策位置"而没有"路径痕迹"，例如 dfs(i) / dfs(i, j) 而不是 dfs(path)。带 path: List[int] 的回溯本质上每条调用栈都是不同的，无法 cache。

桥 2：记忆化搜索 → 自底向上 DP

把记忆化的 dfs(state) 翻译成 dp[state]，按依赖顺序 for 循环填表。LC 322 Coin Change 是经典：

# LC 322 自顶向下记忆化版（回溯 + cache）
@cache
def dfs(amount):
    if amount == 0: return 0
    if amount < 0: return inf
    return min(dfs(amount - c) for c in coins) + 1

# LC 322 自底向上 DP 版（同一个递推关系，循环填表）
dp = [inf] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
    dp[a] = min(dp[a - c] for c in coins if c <= a) + 1

// LC 322 自底向上 DP
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);            // 哨兵代替 inf
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// LC 322 自底向上 DP
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);  // 哨兵代替 inf
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

两种写法等价；选哪种看状态空间——状态稀疏 / 不规则用记忆化（按需算），状态稠密 / 规则用 DP（迭代常数小）。这正是 dp/intro §2 "DP = DAG 拓扑序"的另一个视角。

桥 3：DP → 状压 DP

当回溯的状态包含"已选集合"且集合元素数 ≤ 20 左右时，把集合压成一个 int 的 bitmask，状态就从 path: List[int] 退化成 mask: int。LC 847 Shortest Path Visiting All Nodes 是教科书例子——朴素回溯枚举所有访问顺序是 O(n!)，状压 DP 把状态压成 (node, mask) 后变成 O(2ⁿ · n²)，在 n=12 时差 6 个数量级。

判别信号：

看到 "n ≤ 20 / 15" 而题目要枚举子集 → 状压 DP
看到 "n ≤ 8 / 10" 而题目要枚举排列 → 状压 DP + 起点维度（如 LC 847）
看到 "n ≤ 1000" 且无重复子结构 → 留在回溯，加剪枝即可

一句话总结：回溯写得出来 + 状态无后效性 → 加 @cache 升级记忆化；状态稠密 → 翻成 DP；状态是"已选集合"且 n 小 → 压成 bitmask。这三步进阶在面试官追问"能不能优化"时几乎是标准路径。

Pro 会员

解锁完整北美 OA 题库

165 家公司 / 1000+ 道真题 · Python · Java · C++ 三语题解 · 月度更新

开通会员已是会员，去登录

8. 小结

回溯是 DFS 的一种特化，骨架就是"做选择 → 递归 → 撤销选择"三段式。掌握三件事就能套大部分回溯题：

决策树：先想清楚每一层枚举什么、终止条件是什么，再写代码。
used vs start：顺序敏感（排列）用 used，顺序无关（组合 / 子集）用 start。
剪枝三连：可行性剪枝（目标已不可达）+ 长度剪枝（剩余不够）+ 同层去重（排序后 i > start 跳重复）。

写回溯前先在草稿上画两层决策树，看哪些分支会重复、哪些分支可以剪——画过的题往往代码一次就对。

下一节会进入树与递归的回溯应用——二叉树路径和 / 前序中序构造 / 路径计数。回溯框架不变，只是状态变成"当前节点"而不是"当前下标"。

对应灵神题单：回溯（排列 / 组合 / 子集 / 棋盘）

进一步阅读：灵茶山艾府《回溯题单》；LeetCode Backtracking 标签高频题