回溯算法总结

LightningJie

2026-04-19

c++ › 随笔

C++回溯算法总结

一、前言

回溯算法是算法面试里的高频题型之一。
很多人觉得回溯题“看起来都差不多，但一写就乱”，本质原因通常不是代码能力不够，而是 没有把题型分清楚。

回溯题并不是每一道都要从头想新思路。
实际上，面试中常见的回溯题大多都能归到几类固定模型里：

子集类
组合类
排列类
切割类
棋盘搜索类
带约束的综合搜索类

只要把这些题型的 特征、模板、去重方式、剪枝思路 搞清楚，很多题都能快速识别并套用模板。

这篇文章就从面试实战角度，把常见回溯题系统总结一遍。

二、回溯算法本质是什么

回溯本质上就是：

在一棵决策树上做深度优先搜索，走一步，试一试，不行就退回来，再试别的选择。

所以回溯的核心动作就是四步：

做选择
递归进入下一层
撤销选择
尝试其他选择

最常见的回溯模板如下：

void dfs(状态参数) {
    if (终止条件) {
        收集答案;
        return;
    }

    for (每一种选择) {
        if (当前选择不合法) continue;

        做选择;
        dfs(下一层状态);
        撤销选择;
    }
}

如果题目要求：

求所有方案
枚举所有可能
在尝试过程中需要“选一个、试一下、再撤回”

那大概率就是回溯。

三、面试中最常见的回溯题型分类

回溯题可以大致分成下面 6 类：

子集类
组合类
排列类
切割类
棋盘搜索类
带约束的综合搜索类

下面逐类讲。

四、子集类

1. 题型特征

子集类题目通常长这样：

求一个数组的所有子集
每个元素可以选，也可以不选
最终要求列出所有可能选择方案

典型题目：

LeetCode 78 子集
LeetCode 90 子集 II（有重复元素）

子集类的核心思想是：

对每个元素，考虑“选”或“不选”。

2. 模板一：选 / 不选写法

class Solution {
    vector<vector<int>> res;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int i) {
        if (i == nums.size()) {
            res.push_back(path);
            return;
        }

        // 选 nums[i]
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        path.pop_back();

        // 不选 nums[i]
        dfs(nums, i + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
};

3. 模板二：for 枚举写法

实际面试中，更推荐记这个版本，因为它和组合题模板更统一：

class Solution {
    vector<vector<int>> res;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int start) {
        res.push_back(path);

        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
};

4. 易错点

子集题一个很容易忽略的点是：

子集题通常是“每到一个节点都可以收答案”，而不一定非要等到叶子节点。

因为路径本身就代表一个合法子集。

五、组合类

1. 题型特征

组合类题目通常会让你：

从 n 个数中选 k 个
找所有和为 target 的组合
顺序不同不算不同答案

典型题目：

LeetCode 77 组合
LeetCode 216 组合总和 III
LeetCode 39 组合总和
LeetCode 40 组合总和 II

组合类的核心是：

顺序不重要，所以要通过 start 参数保证只往后选，避免重复。

2. 普通组合：n 选 k

class Solution {
    vector<vector<int>> res;
    vector<int> path;

public:
    void dfs(int n, int k, int start) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }

        for (int i = start; i <= n; i++) {
            path.push_back(i);
            dfs(n, k, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
};

3. 组合总和：元素可以重复使用

例如 LeetCode 39：

class Solution {
    vector<vector<int>> res;
    vector<int> path;

public:
    void dfs(vector<int>& candidates, int target, int start) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;

        for (int i = start; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            dfs(candidates, target - candidates[i], i); // 注意这里是 i
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return res;
    }
};

这里要注意：

递归传的是 i
不是 i + 1

因为当前元素允许重复选。

4. 组合总和 II：元素不能重复使用，且数组中有重复元素

例如 LeetCode 40：

class Solution {
    vector<vector<int>> res;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int target, int start) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;

        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;

            path.push_back(nums[i]);
            dfs(nums, target - nums[i], i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return res;
    }
};

关键点：

先排序
使用“同层去重”：

1	if (i > start && nums[i] == nums[i - 1]) continue;

六、排列类

1. 题型特征

排列类题目通常会让你：

求一个数组的全排列
顺序不同算不同答案

典型题目：

LeetCode 46 全排列
LeetCode 47 全排列 II

排列类和组合类最大的区别是：

排列关心顺序，所以不能仅靠 start 控制，通常要用 used 数组标记元素是否已经被选过。

2. 全排列模板

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

public:
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

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

            dfs(nums);

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

    vector<vector<int>> permute(vector<int>& nums) {
        used.assign(nums.size(), false);
        dfs(nums);
        return res;
    }
};

3. 有重复元素的全排列

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

public:
    void dfs(vector<int>& nums) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(nums[i]);
            dfs(nums);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        used.assign(nums.size(), false);
        dfs(nums);
        return res;
    }
};

去重核心条件：

1	if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

这表示：

当前数字和前一个数字相同，并且前一个数字在当前分支中还没被使用，那么跳过当前数字，避免重复排列。

七、切割类

1. 题型特征

切割类题目通常出现在字符串上，形式一般是：

把字符串切成若干段
每一段都要满足某种条件

典型题目：

LeetCode 131 分割回文串
LeetCode 93 复原 IP 地址

切割类的本质是：

从当前位置开始，尝试把字符串切出一段，判断这一段是否合法，合法则进入下一层继续切。

2. 分割回文串

class Solution {
    vector<vector<string>> res;
    vector<string> path;

public:
    bool isPalindrome(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++;
            r--;
        }
        return true;
    }

    void dfs(string& s, int start) {
        if (start == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = start; i < s.size(); i++) {
            if (!isPalindrome(s, start, i)) continue;

            path.push_back(s.substr(start, i - start + 1));
            dfs(s, i + 1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return res;
    }
};

3. 复原 IP 地址

class Solution {
    vector<string> res;

public:
    bool valid(string& s, int l, int r) {
        if (l > r) return false;
        if (s[l] == '0' && l != r) return false;

        int num = 0;
        for (int i = l; i <= r; i++) {
            if (!isdigit(s[i])) return false;
            num = num * 10 + (s[i] - '0');
        }
        return num >= 0 && num <= 255;
    }

    void dfs(string& s, int start, int part, string path) {
        if (part == 4 && start == s.size()) {
            path.pop_back();
            res.push_back(path);
            return;
        }
        if (part == 4 || start == s.size()) return;

        for (int i = start; i < s.size() && i < start + 3; i++) {
            if (!valid(s, start, i)) continue;
            dfs(s, i + 1, part + 1, path + s.substr(start, i - start + 1) + ".");
        }
    }

    vector<string> restoreIpAddresses(string s) {
        dfs(s, 0, 0, "");
        return res;
    }
};

八、棋盘搜索类

1. 题型特征

棋盘搜索类通常是二维数组 / 棋盘题，例如：

在网格中找路径
在棋盘中放置元素并满足约束

典型题目：

LeetCode 79 单词搜索
LeetCode 51 N 皇后

2. 单词搜索

这是 DFS + 回溯的典型题：

class Solution {
public:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int k) {
        if (k == word.size()) return true;
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
        if (board[i][j] != word[k]) return false;

        char ch = board[i][j];
        board[i][j] = '#';

        bool found = dfs(board, word, i + 1, j, k + 1) ||
                     dfs(board, word, i - 1, j, k + 1) ||
                     dfs(board, word, i, j + 1, k + 1) ||
                     dfs(board, word, i, j - 1, k + 1);

        board[i][j] = ch;
        return found;
    }

    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
};

3. N 皇后

class Solution {
    vector<vector<string>> res;

public:
    bool valid(vector<string>& board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }

        return true;
    }

    void dfs(vector<string>& board, int row, int n) {
        if (row == n) {
            res.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!valid(board, row, col, n)) continue;

            board[row][col] = 'Q';
            dfs(board, row + 1, n);
            board[row][col] = '.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        dfs(board, 0, n);
        return res;
    }
};

九、带约束的综合搜索类

这类题通常不只是单纯的“选或不选”，而是要在搜索过程中满足某种复杂限制。

典型题目：

电话号码的字母组合
括号生成
递增子序列
组合总和系列
火柴拼正方形

1. 电话号码的字母组合

class Solution {
    vector<string> res;
    string path;
    vector<string> mp = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    void dfs(string& digits, int idx) {
        if (idx == digits.size()) {
            res.push_back(path);
            return;
        }

        string letters = mp[digits[idx] - '0'];
        for (char c : letters) {
            path.push_back(c);
            dfs(digits, idx + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        dfs(digits, 0);
        return res;
    }
};

2. 括号生成

class Solution {
    vector<string> res;
    string path;

public:
    void dfs(int n, int left, int right) {
        if (path.size() == 2 * n) {
            res.push_back(path);
            return;
        }

        if (left < n) {
            path.push_back('(');
            dfs(n, left + 1, right);
            path.pop_back();
        }

        if (right < left) {
            path.push_back(')');
            dfs(n, left, right + 1);
            path.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0);
        return res;
    }
};

这个题最重要的剪枝是：

左括号没放满，可以放左括号
右括号数量必须小于左括号数量，才能放右括号

十、回溯题最常见的追问点

面试官很喜欢追问下面这些。

1. 为什么这题适合用回溯？

因为它要求枚举所有可能答案，并且搜索过程中需要“选择 - 递归 - 撤销选择”。

2. 怎么去重？

常见两种：

组合 / 子集去重：同层去重

1	if (i > start && nums[i] == nums[i - 1]) continue;

排列去重：排序 + used 数组

1	if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

3. 怎么剪枝？

常见剪枝思路：

当前和已经超过 target，直接 return
当前长度已经不可能凑出答案，直接返回
当前状态不合法，直接跳过
排序之后，如果后面只会更差，可以直接 break

4. 时间复杂度怎么看？

回溯一般复杂度都不低，常见量级：

子集：O(2^n)
排列：O(n!)
组合：和组合数有关，例如 C(n, k)
棋盘搜索：看搜索树的层数和分支数

面试中通常不要求你给出极其精确的表达式，但至少要能看出是指数级还是阶乘级。

十一、回溯题四大核心模板区别

这是最关键的一部分。

1. 子集

每个元素：选 / 不选
或者从 start 开始往后枚举
每个节点都可能形成一个答案

2. 组合

顺序不重要
通常用 start 保证只往后选
元素能不能重复选，要看递归传 i 还是 i+1

3. 排列

顺序重要
每个位置要选一个没用过的元素
通常用 used 数组

4. 切割

对字符串枚举切割位置
判断当前切出来的一段是否合法
合法才递归下一层

十二、面试高频回溯题清单

下面这些题建议你重点刷熟。

入门必刷

78 子集
77 组合
46 全排列
39 组合总和
131 分割回文串
17 电话号码的字母组合

进阶必刷

90 子集 II
40 组合总和 II
47 全排列 II
93 复原 IP 地址
22 括号生成
79 单词搜索

提升题

51 N 皇后
491 递增子序列
698 划分为 k 个相等的子集
473 火柴拼正方形

十三、面试拿题时的判断口诀

拿到一道看起来像回溯的题，可以先问自己这几个问题：

1. 顺序重要吗？

重要：排列
不重要：组合 / 子集

2. 元素能重复选吗？

能：递归通常传 i
不能：递归通常传 i + 1

3. 数组里有重复元素吗？

有：通常需要排序 + 去重

4. 是在字符串上切吗？

是：切割类

5. 是在二维网格里搜吗？

是：棋盘搜索类

这个判断过程非常有用，很多面试题一眼就能归类。

十四、面试时可以直接说的几句话

下面这些话非常适合在面试中复述：

回溯本质是在决策树上做 DFS。
子集问题通常是每个元素选或不选；
组合问题是从后面继续选，顺序不重要；
排列问题是每个位置选一个没用过的元素，顺序重要；
如果题目有重复元素，一般要先排序，再做去重；
如果题目要求所有方案，并且过程中需要试错和撤销选择，通常就可以考虑回溯。

十五、推荐刷题顺序

建议按下面顺序刷，效果最好：

78 子集
77 组合
39 组合总和
46 全排列
17 电话号码的字母组合
131 分割回文串
90 子集 II
40 组合总和 II
47 全排列 II
22 括号生成
93 复原 IP 地址
79 单词搜索
51 N 皇后

这个顺序是从模板最基础的题型开始，逐步过渡到去重、剪枝和更复杂的约束搜索。

十六、最后总结

回溯题看起来很多，但真正高频的核心模型其实不多。

你最应该掌握的不是“每道题的答案”，而是这几件事：

能快速识别题型
知道该套哪个模板
理解去重和剪枝怎么写
能把思路讲清楚

如果你把下面四个模板彻底吃透：

子集模板
组合模板
排列模板
切割模板

那大多数面试中的回溯题你都能应付。

十七、附：最该背的核心结论

最后用几句话收尾，方便背诵：

回溯就是在决策树上做 DFS
子集是选 / 不选
组合是不关心顺序，从后往后选
排列是关心顺序，要用 used
切割是枚举分割点
有重复元素通常要先排序再去重
回溯题核心不是死记题目，而是认题型和套模板