回溯算法：从八皇后到背包问题的思维体操

回溯算法，说白了就是「试错」——走不通就退回来，换条路再走。我刚开始学算法时，总觉得这玩意儿不就是暴力枚举吗？后来在项目中处理一个排程优化问题，才发现回溯的剪枝技巧能让搜索空间从天文数字降到可接受范围。嗯，今天咱们就把回溯的底裤扒干净。

回溯思想：一条路走到黑，黑了就回头

回溯算法的本质是系统性地枚举所有可能解。它采用深度优先策略，一步步构建解空间树。每走一步，先判断当前路径是否还有希望——有希望就继续深入，没希望就回溯到上一个岔路口。

我个人习惯把回溯算法拆成三个要素：

• 路径：已经做出的选择
• 选择列表：当前可以做的选择
• 结束条件：到达决策树底层，无法再做选择

代码模板其实很固定，你记住这个框架就行：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;  // 这就是回溯的关键
    }
}

我曾经在面试中遇到一个候选人，把回溯写成了递归但忘了撤销选择，结果路径越走越偏。嗯，这个坑咱们得记住。

八皇后问题：经典中的经典

八皇后问题要求在国际象棋棋盘上放置8个皇后，让它们互不攻击。规则很简单：任意两个皇后不能在同一行、同一列或同一对角线上。

你想想看，8×8的棋盘，如果暴力枚举所有放置方式，那得检查C(64,8)种组合——大约44亿种。但用回溯，我们逐行放置，每行只放一个皇后，搜索空间直接降到8! = 40320种。

核心剪枝技巧：用三个布尔数组记录列、主对角线、副对角线的占用情况。

#define N 8
int col[N], diag1[2*N-1], diag2[2*N-1];
int solutions = 0;

void solve(int row) {
    if (row == N) {
        solutions++;
        return;
    }
    for (int c = 0; c < N; c++) {
        if (col[c] || diag1[row+c] || diag2[row-c+N-1])
            continue;  // 冲突，跳过
        // 做选择
        col[c] = diag1[row+c] = diag2[row-c+N-1] = 1;
        solve(row + 1);
        // 撤销选择
        col[c] = diag1[row+c] = diag2[row-c+N-1] = 0;
    }
}

N皇后问题：从八皇后到通用解法

八皇后是N皇后在N=8时的特例。把代码中的N改成任意正整数，就得到了N皇后问题的通用解法。我在项目中遇到过类似的排布问题——在电路板上放置元件，要求元件之间保持安全距离。嗯，思路完全一样，只是约束条件更复杂。

N皇后问题的解空间大小随N增长极快：

N	解的数量	回溯搜索的节点数
4	2	约20
8	92	约2000
10	724	约3万
12	14200	约50万

注意看，N=12时搜索节点数已经到50万了。如果没有剪枝，这个数字会爆炸到12! ≈ 4.79亿。所以说，剪枝不是锦上添花，是雪中送炭。

全排列问题：回溯的入门练习

全排列问题要求输出一个数组的所有排列方式。比如[1,2,3]的全排列有6种：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。

用回溯解决全排列，思路非常直观：

• 每次从剩余元素中选一个放到当前位置
• 用used数组标记哪些元素已经用过
• 当路径长度等于数组长度时，记录结果

void permute(int* nums, int n, int* path, int* used, int depth) {
    if (depth == n) {
        // 打印或记录path
        return;
    }
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        path[depth] = nums[i];
        used[i] = 1;
        permute(nums, n, path, used, depth + 1);
        used[i] = 0;  // 回溯
    }
}

全排列问题有个变种——包含重复元素的全排列。这时候需要先排序，然后加一个剪枝条件：如果当前元素和前一个相同，且前一个还没用过，就跳过。为什么？因为相同元素在同一层重复选择会产生重复排列。

0-1背包问题（回溯解法）：暴力搜索的艺术

0-1背包问题：有N个物品，每个物品有重量w[i]和价值v[i]，背包容量为C。问如何选择物品使得总价值最大，且总重量不超过容量。

回溯解法就是枚举每个物品「选」或「不选」两种状态，形成一棵二叉树。搜索过程中记录当前总重量和总价值，到达叶子节点时更新最优解。

int bestValue = 0;
void knapsack(int i, int curW, int curV, int n, int C, int* w, int* v) {
    if (i == n) {
        if (curV > bestValue) bestValue = curV;
        return;
    }
    // 不选第i个物品
    knapsack(i+1, curW, curV, n, C, w, v);
    // 选第i个物品（如果装得下）
    if (curW + w[i] <= C) {
        knapsack(i+1, curW + w[i], curV + v[i], n, C, w, v);
    }
}

这个朴素回溯的时间复杂度是O(2^N)，N稍微大一点就跑不动了。我在项目中处理过N=50的背包问题，纯回溯跑了三天三夜没出结果。后来加了剪枝——计算剩余物品的最大可能价值，如果当前价值+剩余最大价值 ≤ 当前最优解，直接剪掉。

回溯算法的知识体系

下面这张图总结了回溯算法的核心脉络，我建议你多看几遍：

回溯算法的实用技巧

做了这么多年嵌入式开发，我总结了几条回溯算法的实战经验：

1. 先画决策树：动手写代码前，先在纸上画出N=3或N=4的决策树。这能帮你理清递归深度和分支逻辑。
2. 剪枝要趁早：剪枝条件越早判断越好，最好在进入递归前就过滤掉无效分支。我在背包问题中把剪枝放在递归入口，性能提升了10倍。
3. 状态重置要彻底：撤销选择时，确保所有修改过的全局状态都恢复原样。漏掉一个，bug就来了。
4. 用引用传递减少拷贝：路径数组用指针传递，避免递归层数深时的大量内存拷贝。C语言里这就是基本功。
5. 对称性剪枝：如果问题有对称性（比如棋盘旋转对称），可以只搜索一个等价类，然后通过对称变换生成其他解。

回溯算法虽然看起来简单，但真正用好它需要大量练习。我建议你从全排列开始练手，然后挑战N皇后，最后啃0-1背包的剪枝优化。每道题至少手写三遍——第一遍理解思路，第二遍优化剪枝，第三遍做到bug free。

嗯，回溯这块就聊到这儿。记住那个口诀：做选择，递归，撤销选择。这是回溯的灵魂。