回溯法（Backtracking）是一种系统搜索问题解的方法，核心思想是：从初始状态出发，按照一定规则逐步尝试构造解；当发现当前选择无法得到有效解时，就撤销上一步甚至多步的选择，换一条路径继续尝试。
它本质上是 深度优先搜索 + 剪枝 + 状态重置，常用来解决“搜索所有解”“搜索任意一个解”“在约束条件下求最优解”的问题。
一、回溯法的基本概念
1. 解空间
一个问题所有可能的解构成的集合，称为该问题的解空间。
例如：
- 求集合
{1,2,3}的全排列，解空间由3! = 6个排列组成； - 求
n个元素的子集，解空间大小为2^n； n皇后问题，解空间大小为n!左右。
回溯法通常将解空间组织成一棵树，称为解空间树，然后在树上进行深度优先搜索。
2. 两类典型解空间树
- 子集树：每个元素有“选”或“不选”两种可能，例如子集问题、0/1背包问题。
如果问题规模为n，子集树最多有2^n个叶子节点。 - 排列树：每个位置从剩余元素中选择一个，例如全排列、旅行商问题、N皇后问题。
如果问题规模为n，排列树最多有n!个叶子节点。
3. 剪枝函数
回溯法不是完全暴力搜索，它会在搜索过程中使用剪枝函数去掉不可能产生解的子树。
剪枝函数分为两类：
- 约束函数：剪掉不满足约束条件的子树。
例如：N皇后中，当前放置位置会与已有皇后冲突，就不继续搜索。 - 限界函数：剪掉不可能得到最优解的子树。
例如：0/1背包中，即使把剩余所有物品都装进去，总价值也无法超过当前最优值，就剪掉。
二、回溯法的核心三要素
使用回溯法时，通常围绕三个量展开：
- 路径：已经做出的选择。
- 选择列表：当前还可以做出的选择。
- 结束条件：到达解空间树底部，或者已经找到一个可行解，无法再继续选择。
这三个要素对应回溯算法的递归函数结构。
三、回溯法通用模板
回溯法可以用递归实现，伪代码非常统一：
vector<vector<int>> result; // 保存所有可行解
void backtrack(vector<int>& path, vector<int>& choices) {
if (满足结束条件) {
result.push_back(path); // 注意：不能直接保存引用
return;
}
for (int choice : choices) {
if (!is_valid(choice, path)) {
continue; // 剪枝
}
path.push_back(choice); // 做选择
backtrack(path, get_choices(choice));
path.pop_back(); // 撤销选择
}
}
C++ 风格的通用模板：
void backtrack(vector<int>& path, vector<vector<int>>& result) {
if (is_goal(path)) {
result.push_back(path); // 拷贝路径
return;
}
for (int choice : get_choices(path)) {
if (!is_valid(choice, path)) {
continue;
}
path.push_back(choice); // 做选择
backtrack(path, result);
path.pop_back(); // 撤销选择
}
}
要点：
- 递归前“做选择”，递归后“撤销选择”。
- 保存结果时要复制当前路径，例如
result.push_back(path)。 - 剪枝条件可以放在进入递归前，以减少不必要的递归。
四、经典问题详解
1. 全排列问题
问题：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
决策思路：
- 每次从剩余数字中选择一个加入当前排列。
- 用一个
used数组记录哪些数字已经被选过。 - 当排列长度等于原数组长度时，找到一个完整排列。
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> used(nums.size(), false);
function<void()> backtrack = [&]() {
if (path.size() == nums.size()) {
result.push_back(path); // 拷贝路径
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack();
path.pop_back(); // 撤销选择
used[i] = false; // 恢复状态
}
};
backtrack();
return result;
}
};
如果数组中有重复元素，需要先排序，然后跳过同一层中重复的分支：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
这样可以保证相同数字在同一层只被使用一次，避免重复排列。
2. 组合问题
问题：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
决策思路：
- 为避免
[1,2]和[2,1]这种重复，使用start索引，保证选择顺序递增。 - 每次从
start开始向后选择，下一次递归从i + 1开始。
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> path;
function<void(int)> backtrack = [&](int start) {
if (path.size() == k) {
result.push_back(path);
return;
}
// 剪枝：如果剩余可选数不够凑齐 k 个，就直接返回
// i <= n - (k - path.size()) + 1
int end = n - (k - path.size()) + 1;
for (int i = start; i <= end; ++i) {
path.push_back(i);
backtrack(i + 1);
path.pop_back();
}
};
backtrack(1);
return result;
}
};
剪枝条件：
i <= n - (k - path.size()) + 1
含义是：还需要选 k - path.size() 个数，当前最多只能选到 n - (k - path.size()) + 1，否则剩余数量不够。
3. 子集问题
问题：给定一个整数数组 nums，返回其所有子集。
决策思路：
- 每个元素有“选”和“不选”两种状态。
- 也可以看成组合问题，长度为 0 到
n的所有组合。
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
function<void(int)> backtrack = [&](int start) {
result.push_back(path); // 每个节点都是一个子集
for (int i = start; i < nums.size(); ++i) {
path.push_back(nums[i]);
backtrack(i + 1);
path.pop_back();
}
};
backtrack(0);
return result;
}
};
如果数组中有重复元素，可以排序后：
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
这样就能跳过同一层的重复元素。
4. N皇后问题
问题：在 n × n 的棋盘上放置 n 个皇后，使它们彼此不能攻击。皇后可以攻击同一行、同一列以及两条对角线上的棋子。
决策思路：
- 逐行放置皇后。
- 每一行中尝试所有列，检查是否与已放置的皇后冲突。
- 用集合记录已经占用的列和对角线。
对角线表示方法：
- 主对角线：
row - col为定值； - 副对角线：
row + col为定值。
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<string> board(n, string(n, '.'));
unordered_set<int> cols, diag1, diag2;
function<void(int)> backtrack = [&](int row) {
if (row == n) {
result.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
int d1 = row - col;
int d2 = row + col;
if (cols.count(col) || diag1.count(d1) || diag2.count(d2)) {
continue; // 冲突，剪枝
}
// 做选择
board[row][col] = 'Q';
cols.insert(col);
diag1.insert(d1);
diag2.insert(d2);
backtrack(row + 1);
// 撤销选择
board[row][col] = '.';
cols.erase(col);
diag1.erase(d1);
diag2.erase(d2);
}
};
backtrack(0);
return result;
}
};
时间复杂度大约为 O(n!)，但剪枝后实际运行时间会远小于这个上界。
5. 括号生成
问题：生成 n 对有效括号的所有组合。
约束条件：
- 左括号数量不能超过
n； - 右括号数量不能超过左括号数量。
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
string path;
function<void(int, int)> backtrack = [&](int left, int right) {
if (path.size() == 2 * n) {
result.push_back(path);
return;
}
if (left < n) {
path.push_back('(');
backtrack(left + 1, right);
path.pop_back();
}
if (right < left) { // 右括号数量必须小于左括号
path.push_back(')');
backtrack(left, right + 1);
path.pop_back();
}
};
backtrack(0, 0);
return result;
}
};
6. 单词搜索
问题：给定一个 m × n 的字符网格和一个单词，判断该单词是否存在于网格中。单词必须按照字母顺序通过相邻单元格组成，同一单元格不能重复使用。
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size();
int cols = board[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
function<bool(int, int, int)> backtrack = [&](int r, int c, int index) {
if (index == word.size()) {
return true;
}
if (r < 0 || r >= rows || c < 0 || c >= cols
|| visited[r][c] || board[r][c] != word[index]) {
return false;
}
visited[r][c] = true;
for (auto [dr, dc] : directions) {
if (backtrack(r + dr, c + dc, index + 1)) {
return true;
}
}
visited[r][c] = false; // 回溯
return false;
};
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (board[i][j] == word[0]) {
if (backtrack(i, j, 0)) {
return true;
}
}
}
}
return false;
}
};
7. 分割回文串
问题：给定字符串 s，将其分割成一些子串，使每个子串都是回文串，返回所有可能的分割方案。
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
int n = s.size();
function<bool(int, int)> is_palindrome = [&](int left, int right) {
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
};
function<void(int)> backtrack = [&](int start) {
if (start == n) {
result.push_back(path);
return;
}
for (int end = start; end < n; ++end) {
if (is_palindrome(start, end)) {
path.push_back(s.substr(start, end - start + 1));
backtrack(end + 1);
path.pop_back();
}
}
};
backtrack(0);
return result;
}
};
8. 数独求解
数独是回溯法的典型应用：在一个 9 × 9 的格子中填入数字 1~9，要求每行、每列、每个 3 × 3 宫内数字不重复。
基本步骤：
- 找到一个空格；
- 尝试填入
1~9； - 如果某个数字合法，则填进去，递归处理下一个空格；
- 如果后续无解，则撤销当前填入，尝试下一个数字。
#include <vector>
using namespace std;
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
function<bool(int, int, char)> is_valid = [&](int row, int col, char num) {
for (int i = 0; i < 9; ++i) {
if (board[row][i] == num) return false;
if (board[i][col] == num) return false;
}
int box_row = row / 3 * 3;
int box_col = col / 3 * 3;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (board[box_row + i][box_col + j] == num) return false;
}
}
return true;
};
function<bool()> backtrack = [&]() {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
for (char num = '1'; num <= '9'; ++num) {
if (is_valid(i, j, num)) {
board[i][j] = num;
if (backtrack()) {
return true;
}
board[i][j] = '.'; // 回溯
}
}
return false; // 1~9 都试完仍无解
}
}
}
return true; // 没有空格，求解成功
};
backtrack();
}
};
五、剪枝与优化技巧
剪枝是回溯法的效率关键。常用的剪枝策略有：
1. 可行性剪枝
当前选择已经无法满足约束条件时，立即停止搜索该分支。
例如：
- N皇后中列和对角线冲突；
- 数独中数字重复；
- 括号生成中右括号多于左括号。
2. 最优性剪枝
在求最优解的问题中，如果当前部分解已经不可能优于已有最优解，则剪掉。
例如：
- 0/1背包中，即使剩余物品全选也不能超过当前最优价值；
- 旅行商问题中，当前路径长度已经大于最短路径。
3. 顺序优化
在搜索前对候选集合进行排序，优先选择限制条件多的分支，往往能减少搜索量。
例如：
- 数独中优先填可填数字最少的空格；
- 组合问题中先排序再去重。
4. 去重剪枝
对于有重复元素的问题，排序后在同一层递归中跳过相同元素：
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
在排列问题中使用 used 数组去重：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
5. 对称性剪枝
利用问题的对称性减少搜索空间。
例如 N皇后问题，第一行皇后只需要放在一半列上，然后通过对称得到其余解。
六、复杂度分析
回溯法的时间复杂度通常较高，一般与解空间大小有关。
1. 子集树
如果每个元素有两种选择，则解空间大小为 O(2^n)。
例如子集问题、0/1背包问题。
时间复杂度：
O(2^n)
2. 排列树
如果每个位置有递减的选择数量，则解空间大小为 O(n!)。
例如全排列、N皇后、旅行商问题。
时间复杂度：
O(n!)
3. 空间复杂度
主要取决于递归深度：
O(n)
其中 n 是问题规模。如果路径需要存储，空间可能为 O(n) 或更深。
由于剪枝的存在，实际运行时间可能远小于理论最坏复杂度，但最坏情况下仍然是指数级。
七、回溯法与其他算法的关系
1. 回溯法与深度优先搜索（DFS）
回溯法通常是基于 DFS 实现的。
区别在于：
- DFS 强调遍历所有节点；
- 回溯强调“状态重置”和“剪枝”，在搜索过程中不断尝试、撤销。
可以认为回溯法 = DFS + 剪枝 + 状态恢复。
2. 回溯法与动态规划（DP）
- 回溯法适合搜索所有解或判断是否存在可行解；
- 动态规划适合求最优解，并且问题具有重叠子问题和最优子结构；
- 回溯法可以通过记忆化搜索的方式避免重复计算，接近动态规划。
例如“单词拆分”可以用回溯，也可以用动态规划。回溯+记忆化后复杂度可以接近 DP。
3. 回溯法与分支限界法
- 回溯法是深度优先搜索，沿着一条路径一直走到底，不行再退回；
- 分支限界法是广度优先或最小耗费优先搜索，常用于求最优解；
- 分支限界法通常维护一个队列或优先队列，扩展节点后按某种策略选择下一个节点。
4. 回溯法与贪心算法
贪心算法每步做出局部最优选择，不回溯；
回溯法会尝试多种选择，并在不合适时撤销，因此更通用但更慢。
八、常见错误与注意事项
1. 忘记撤销选择
path.push_back(x);
backtrack(...);
// 忘记 path.pop_back();
会导致不同分支之间状态污染。
2. 保存结果时没有复制路径
result.push_back(path);
这样后续修改 path 时，已保存的结果也会变化。应使用：
result.push_back(path); // vector 会拷贝内容，但若 path 是指针或引用则不行
或：
result.push_back(vector<int>(path));
3. 修改全局状态后未恢复
例如使用了 visited、used、棋盘、集合等，递归返回后必须恢复到递归前的状态。
4. 剪枝条件写错
比如组合问题中 start 的更新、排列去重的条件，写错会导致漏解或重复解。
5. 递归条件不明确
一定要清楚：
- 什么时候结束？
- 什么时候递归？
- 递归前后状态如何变化？
九、总结
回溯法的核心可以总结为四步：
- 定义解空间：明确解的结构，确定搜索树；
- 确定递归参数：路径、选择列表、当前状态；
- 编写递归函数：
- 判断是否达到结束条件；
- 遍历所有选择；
- 做选择 → 递归 → 撤销选择；
- 加入剪枝：尽早排除不可能的分支。
回溯法适合解决的问题通常具有以下特征：
- 需要搜索所有可行解，或任意一个可行解；
- 解空间可以用树表示；
- 没有多项式时间的直接算法；
- 可以通过约束条件大幅剪枝。
掌握回溯法的核心模板后，遇到全排列、组合、子集、N皇后、数独、迷宫、括号生成、分割回文串等问题，都可以比较顺利地解决。
希望这篇博客能帮你透彻理解回溯法，并在实际编码中灵活运用。如果对某个问题有疑问，欢迎进一步交流！