在算法面试和日常开发中，回溯算法 (Backtracking) 是一种非常重要且通用的算法思想。
全排列、组合、切割、子集、N 皇后、数独……这些看似毫无关联的难题，本质上都可以用同一套"回溯模板"解决。
本文会从思想出发，配合 4 套渐进式的 C++ 代码（无重复排列、含重复排列、无重复组合、含重复组合），带你一次性彻底搞懂回溯。

---

1. 什么是回溯？

简单来说，回溯法就是一种暴力搜索算法：通过分步地尝试去解决一个问题，一旦发现当前分步无法得到有效解，就撤销上一步（甚至是上几步）的操作，换另一条路继续尝试。

你可以把它想象成走迷宫：

1. 站在一个岔路口 —— 做选择
2. 选择一条路走下去 —— 递归
3. 发现走到了死胡同 —— 不满足条件
4. 退回到上一个岔路口 —— 回溯
5. 撤销刚才的选择，换一条路 —— 撤销操作

所以回溯法的核心本质是：

递归 + 剪枝，它遍历的其实是一棵决策树。

---

2. 回溯算法的通用模板

所有的回溯问题，都可以套用下面这套"万能钥匙"伪代码：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择 : 本层集合中的元素) {
        处理节点;                        // 做选择
        backtracking(路径, 选择列表);    // 递归进入下一层
        撤销处理;                        // 回溯 —— 关键步骤
    }
}

核心三要素

1. 路径 (path)：已经做出的选择。
2. 选择列表 (choices)：当前还可以进行哪些选择。
3. 终止条件 (base case)：到达决策树底层，无法再做选择。

理解了这三要素，下面所有的问题就只是"模板套用 + 少许变化"而已。

---

3. 经典案例一：全排列（无重复数字）

LeetCode 46. Permutations
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

思路

排列问题讲究顺序，[1, 2] 和 [2, 1] 是两个不同的结果。因此：

• 每一层递归都要从头 0 开始遍历 nums；
• 需要一个 used 数组标记哪些数字在当前路径上已经被使用过，防止同一个数字被重复选取。

决策树示意

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

C++ 实现

#include <vector>
using namespace std;

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(const vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.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]);

            backtracking(nums, used);       // 递归

            path.pop_back();                // 撤销选择
            used[i] = false;
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

---

4. 经典案例二：全排列（含重复数字）

LeetCode 47. Permutations II
给定一个可能包含重复数字的数组 nums，返回不重复的全排列。
例如 nums = [1, 1, 2]，应返回 [[1,1,2], [1,2,1], [2,1,1]]，而不能出现两次 [1,1,2]。

难点：去重

由于存在重复数字，朴素回溯会产生重复的排列。
去重的关键是回答两个问题：

1. 哪里去重？ —— 在**同一层（同一父节点下的兄弟分支）**之间去重。
2. 怎么去重？ —— 先排序，让相同的数字相邻，然后利用 used 数组判断"上一个相同数字是否在同层已经用过"。

重点理解这句话：

• used[i-1] == false：说明 nums[i-1] 已经被"回溯撤销"了，它和 nums[i] 是同一层上的两个相同数字 —— 需要剪枝。
• used[i-1] == true：说明 nums[i-1] 还在当前路径上，nums[i] 是它的子层选择 —— 合法，不能剪。

这就是著名的**“树层去重” vs “树枝去重”**。

C++ 实现

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(const vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }

        for (int i = 0; i < (int)nums.size(); i++) {
            // 同层去重：前一个相同数字已经被撤销过，当前这个就不要再用了
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            if (used[i]) continue;

            used[i] = true;
            path.push_back(nums[i]);

            backtracking(nums, used);

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

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        result.clear();
        path.clear();
        sort(nums.begin(), nums.end());     // 去重的前提：先排序
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

小贴士：把去重条件改成 used[i - 1] == true 也能 AC，但效率会低一些，因为它是"树枝去重"——剪掉的分支更少。推荐使用 !used[i - 1] 的树层去重写法。

---

5. 经典案例三：组合（无重复数字）

LeetCode 77. Combinations
给定两个整数 n 和 k，返回 1 .. n 中所有可能的 k 个数的组合。

思路

与排列最大的区别是：组合不讲究顺序，[1,2] 和 [2,1] 算同一个组合。

为了避免重复，引入一个 startIndex 参数：

• 第一层从 1 开始选；
• 下一层只能从 i + 1 开始选，永远"向前看，不回头"。

剪枝优化

假设 n = 4, k = 4，当前 path 为空，还需要再选 4 个数。
那么即使 i = 2，后面也只剩 2, 3, 4 三个数，凑不齐 4 个。
因此遍历上界可以收紧为：

i <= n - (k - path.size()) + 1

这是一个非常常用的组合剪枝公式，能把暴力搜索的规模砍掉一大截。

C++ 实现

#include <vector>
#include <iostream>
using namespace std;

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(int n, int k, int startIndex) {
        if ((int)path.size() == k) {
            result.push_back(path);
            return;
        }

        // 剪枝：还需要 (k - path.size()) 个元素，i 最大只能到 n - (k - path.size()) + 1
        for (int i = startIndex; i <= n - (k - (int)path.size()) + 1; i++) {
            path.push_back(i);              // 做选择
            backtracking(n, k, i + 1);      // 下一层从 i+1 开始
            path.pop_back();                // 撤销选择
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        result.clear();
        path.clear();
        backtracking(n, k, 1);
        return result;
    }
};

int main() {
    Solution sol;
    int n = 4, k = 2;
    auto res = sol.combine(n, k);

    cout << "从 " << n << " 个数中选 " << k << " 个数的组合：\n";
    for (const auto& vec : res) {
        cout << "[ ";
        for (int x : vec) cout << x << " ";
        cout << "]\n";
    }
    return 0;
}

输出：

从 4 个数中选 2 个数的组合：
[ 1 2 ]
[ 1 3 ]
[ 1 4 ]
[ 2 3 ]
[ 2 4 ]
[ 3 4 ]

---

6. 经典案例四：组合（含重复数字 / 目标和）

LeetCode 40. Combination Sum II
给定一个可能包含重复数字的候选数组 candidates 和一个目标值 target。
找出 candidates 中所有可以使数字和为 target 的组合，每个数字在每个组合中只能使用一次，且解集不能包含重复的组合。

例如 candidates = [10, 1, 2, 7, 6, 1, 5], target = 8，应返回：

[[1,1,6], [1,2,5], [1,7], [2,6]]

这个问题同时包含了组合和重复元素去重两个要点，是对前面所有知识点的综合考验。

去重思想

和"含重复数字的排列"一样：

1. 先 sort 让相同数字相邻；
2. 在同一层（for 循环）里，相同数字只能选一次；
3. 但跨层（递归调用）时可以继续使用（因为题目说"每个数字只能用一次"，但指的是数组下标，不是数值）。

去重条件：i > startIndex && candidates[i] == candidates[i - 1]。

• i > startIndex 表明我们现在在同层的第二个（及以后）分支上；
• 和前面"排列去重"的 !used[i-1] 等价，但借助 startIndex 写起来更直观。

C++ 实现

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtracking(const vector<int>& candidates, int target,
                      int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex;
             i < (int)candidates.size() && sum + candidates[i] <= target;  // 剪枝：已排序，后面更大
             i++) {
            // 同层去重：同一层里相同的数字只能选一次
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }

            sum += candidates[i];
            path.push_back(candidates[i]);

            backtracking(candidates, target, sum, i + 1);   // i+1：每个数字只能用一次

            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

如果题目要求"每个数字可以无限次使用"（LeetCode 39. Combination Sum），只需把递归调用里的 i + 1 改成 i 即可：同一个下标允许被反复选取。

---

7. 排列 vs 组合：一张表看懂区别

特性	排列 (Permutation)	组合 (Combination)
是否讲顺序	讲究顺序（[1,2] ≠ [2,1]）	不讲顺序（[1,2] == [2,1]）
控制手段	used 数组	startIndex 变量
每层遍历	从头 0 开始，跳过已 used	从 startIndex 开始，绝不回头
有重去重	排序 + !used[i-1]（树层去重）	排序 + i > startIndex && 相等则跳过

---

8. 什么时候使用回溯算法？

通常遇到以下类型的问题，可以优先考虑回溯：

1. 组合问题：N 个数里按一定规则找出 k 个数的集合。
2. 切割问题：一个字符串按一定规则有几种切割方式（如分割回文串）。
3. 子集问题：一个 N 个数的集合里有多少符合条件的子集。
4. 排列问题：N 个数按一定规则的全排列。
5. 棋盘问题：N 皇后、解数独、走迷宫等。

识别它们的一个通用信号是：“枚举所有可行解”，而不是"求最优值"或"求可行解的数量"（后两者更多是 DP 的地盘）。

---

9. 复杂度与性能

回溯算法的时间复杂度通常很高，因为它本质上是在枚举决策树的所有路径：

问题类型	典型时间复杂度	空间复杂度
全排列	O(n * n!)	O(n) 递归栈
组合	O(C(n, k) * k)	O(k) 递归栈
子集	O(n * 2^n)	O(n) 递归栈
N 皇后	约 O(n!)	O(n^2) 棋盘

所以剪枝在回溯中极其重要，常见手段包括：

1. 可行性剪枝：当前状态已经不可能得到解，直接返回（如上面的 sum + x > target）。
2. 数量剪枝：剩余元素数量不足以凑出解（如组合里的 n - (k - path.size()) + 1）。
3. 去重剪枝：同层相同元素只走一次（即"树层去重"）。

---

10. 总结

回溯算法并不神秘，它就是带有状态撤销功能的深度优先搜索 (DFS)。

• 优点：逻辑清晰，几乎能搞定所有"枚举所有可行解"的问题。
• 缺点：时间复杂度通常是指数级的，属于"暴力解法"，需要靠剪枝优化性能。

学习回溯的关键，其实就集中在三件事上：

1. "做选择"与"撤销选择"必须对称，这是回溯的灵魂；
2. 区分何时用 startIndex（组合/子集）与何时用 used（排列）；
3. 有重复元素时先排序，再通过"树层去重"的条件剪枝。

把这三点吃透，再回头看任何一道"像是回溯"的题目，你都会有一种"万变不离其宗"的从容感。

---

Happy Coding!