回溯法：一种“试错”的智慧

回溯法，说白了就是一种“走不通就回头”的算法思想。我个人觉得，它是所有算法里最贴近人类思考方式的一种。你想想看，我们做决策时，不也是先试试这条路，不行再换一条吗？

回溯法的核心，就是深度优先搜索 + 剪枝。它会在所有可能的解空间里，系统地搜索目标解。一旦发现当前路径不可能得到解，就立即回溯到上一个状态，换条路继续走。

回溯法的基本框架

我习惯把回溯法写成这样一个模板：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    for (选择 : 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }
}

嗯，这里要注意：撤销选择这一步特别关键。我见过不少新手，写回溯法时忘了撤销选择，结果路径越走越乱，最后得到一堆错误答案。

典型问题一：八皇后

八皇后问题，是回溯法的经典入门题。要求在一个8×8的棋盘上放置8个皇后，让它们互相不能攻击。

我在项目中遇到过类似的问题——一个排课系统，要安排8门课到不同时间段，每门课不能冲突。当时我第一反应就是：这不就是八皇后吗？

#include <stdio.h>
#include <stdbool.h>

#define N 8

int board[N][N] = {0};
int solutions = 0;

bool isSafe(int row, int col) {
    // 检查列
    for (int i = 0; i < row; i++)
        if (board[i][col]) return false;
    
    // 检查左上对角线
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
        if (board[i][j]) return false;
    
    // 检查右上对角线
    for (int i = row, j = col; i >= 0 && j < N; i--, j++)
        if (board[i][j]) return false;
    
    return true;
}

void solveNQueens(int row) {
    if (row == N) {
        solutions++;
        return;
    }
    
    for (int col = 0; col < N; col++) {
        if (isSafe(row, col)) {
            board[row][col] = 1;  // 放置皇后
            solveNQueens(row + 1);
            board[row][col] = 0;  // 撤销皇后
        }
    }
}

int main() {
    solveNQueens(0);
    printf("八皇后共有 %d 种解法\n", solutions);
    return 0;
}

典型问题二：0-1背包

0-1背包问题，每个物品要么拿要么不拿，不能拆分。回溯法解决这个问题，本质上就是枚举所有组合。

我曾经用回溯法做过一个资源分配系统，要在有限预算下选择最优的项目组合。嗯，和0-1背包一模一样。

#include <stdio.h>

#define N 4  // 物品数量
#define W 8  // 背包容量

int weights[N] = {2, 3, 4, 5};
int values[N] = {3, 4, 5, 6};
int maxValue = 0;

void knapsack(int index, int currentWeight, int currentValue) {
    if (index == N) {
        if (currentValue > maxValue)
            maxValue = currentValue;
        return;
    }
    
    // 不选当前物品
    knapsack(index + 1, currentWeight, currentValue);
    
    // 选当前物品（如果能装下）
    if (currentWeight + weights[index] <= W) {
        knapsack(index + 1, 
                 currentWeight + weights[index], 
                 currentValue + values[index]);
    }
}

int main() {
    knapsack(0, 0, 0);
    printf("最大价值: %d\n", maxValue);
    return 0;
}

典型问题三：图的着色

图的着色问题，要求用m种颜色给图的每个顶点着色，使得相邻顶点颜色不同。这在地图着色、寄存器分配等场景中都有应用。

我记得有一次做编译器后端优化，要用图着色算法分配寄存器。当时我直接套用了回溯法的框架，很快就搞定了。

#include <stdio.h>
#include <stdbool.h>

#define V 4  // 顶点数

int graph[V][V] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 1},
    {1, 0, 1, 0}
};

int colors[V] = {0};  // 颜色编号从1开始
int m = 3;  // 颜色数

bool isSafe(int v, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && colors[i] == c)
            return false;
    }
    return true;
}

bool graphColoring(int v) {
    if (v == V) return true;
    
    for (int c = 1; c <= m; c++) {
        if (isSafe(v, c)) {
            colors[v] = c;
            if (graphColoring(v + 1))
                return true;
            colors[v] = 0;  // 回溯
        }
    }
    return false;
}

int main() {
    if (graphColoring(0)) {
        printf("着色方案: ");
        for (int i = 0; i < V; i++)
            printf("%d ", colors[i]);
        printf("\n");
    } else {
        printf("无法用%d种颜色着色\n", m);
    }
    return 0;
}

回溯法的核心逻辑

下面这张图，是我自己总结的回溯法执行流程，希望能帮你理清思路：

回溯法的时间复杂度

回溯法的时间复杂度，通常是指数级的。具体来说：

问题	时间复杂度	说明
八皇后	O(N!)	N个皇后，每行一个，排列组合
0-1背包	O(2^N)	每个物品选或不选
图的着色	O(m^N)	m种颜色，N个顶点

我的经验总结

回溯法用得好不好，关键看三点：

• 状态定义要清晰——路径里存什么，选择列表是什么，边界条件是什么
• 剪枝要狠——能提前判断的，绝不等到最后
• 撤销操作要完整——做过什么选择，就要原样撤销

我曾经在一个项目中，因为忘了撤销一个全局变量的修改，导致整个搜索空间都乱了。排查了整整一个下午才找到问题。从那以后，我每次写回溯法，都会在撤销操作那里加个注释，提醒自己。

回溯法，说白了就是“试错”的艺术。它不追求一步到位，而是通过不断的尝试和回退，最终找到正确答案。这种思想，不仅在算法中有用，在生活中也很有启发——遇到困难时，不妨退一步，换个方向再试试。

---

公众号:蓝海资料掘金营，微信deep3321