回溯算法详解与典型应用
回溯法是一种经典的暴力搜索策略，通常用于解决需要找出所有可行解的问题。它的本质是深度优先搜索（DFS），通过构建一棵隐式决策树来系统地探索各种可能性。每当发现当前路径无法通向有效解时，就会撤销上一步的选择并尝试其他路径，这种"试探—失败—回退—再试探"的机制正是回溯的核心思想。
整个流程可以概括为以下三步：
- 选择：在当前节点做出一个局部决策
- 递归：基于该选择进入下一个状态继续处理
- 撤销：退出递归后恢复现场，以便测试其余选项
设计回溯程序前需考虑清楚三个关键点：
- 当前所处的状态是什么？比如已选取的元素集合、当前位置等。
- 此时还可以做哪些选择？
- 何时满足终止条件并将当前结果加入最终答案？
只要这三个方面清晰明了，就能较容易地写出正确的回溯逻辑。
回溯算法通用结构
大部分回溯问题都遵循如下基本形式：
void backtrack(状态参数) {
if (达到终止条件) {
记录结果;
return;
}
for (每个可选分支) {
if (剪枝条件不满足) continue;
做出选择;
backtrack(新状态);
撤销选择;
}
}
这是理解各类具体问题的基础模板。
典型应用场景分析
根据题目类型的不同，常见的回溯模型大致可分为以下几种：
枚举子集
对于给定数组生成全部子集的问题，空集也属于合法输出之一，因此应在函数入口处立即保存当前路径作为其中一个解。
示例代码片段如下：
int** subsets(int* nums, int size, int* count, int** colSizes) {
int max = 1 << size;
int** res = malloc(max * sizeof(int*));
*colSizes = malloc(max * sizeof(int));
int* path = malloc(size * sizeof(int));
int len = 0;
void dfs(int idx) {
res[*count] = malloc(len * sizeof(int));
memcpy(res[*count], path, len * sizeof(int));
(*colSizes)[(*count)++] = len;
for (int i = idx; i < size; ++i) {
path[len++] = nums[i];
dfs(i + 1);
--len;
}
}
*count = 0;
dfs(0);
return res;
}
注意每次调用都要复制一份当前路径内容以避免后续修改影响已有数据。
组合构造
组合问题是要求从 1 到 n 中选出长度为 k 的不同数字序列。这类问题往往涉及重复项去除的操作，一般采用排序+跳过相邻相等元素的方式实现层级去重。
示例实现：
int** combine(int n, int k, int* rows, int** cols) {
int cap = 10000;
int** res = malloc(cap * sizeof(int*));
*cols = malloc(cap * sizeof(int));
int* buf = malloc(k * sizeof(int));
int pos = 0;
void search(int start) {
if (pos == k) {
res[*rows] = malloc(k * sizeof(int));
memcpy(res[*rows], buf, k * sizeof(int));
(*cols)[(*rows)++] = k;
return;
}
for (int i = start; i <= n; ++i) {
buf[pos++] = i;
search(i + 1);
--pos;
}
}
*rows = 0;
search(1);
return res;
}
排列生成
与组合不同的是，在排列中顺序是有意义的。因此每一轮迭代都要从头开始遍历，并借助辅助数组标记已被使用的元素。
参考代码：
int** permute(int* nums, int n, int* total, int** sizes) {
int limit = 720; // 预估最大情况数量
int** result = malloc(limit * sizeof(int*));
*sizes = malloc(limit * sizeof(int));
int* used = calloc(n, sizeof(int));
int* temp = malloc(n * sizeof(int));
int depth = 0;
void generate() {
if (depth == n) {
result[*total] = malloc(n * sizeof(int));
memcpy(result[*total], temp, n * sizeof(int));
(*sizes)[(*total)++] = n;
return;
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
used[i] = 1;
temp[depth++] = nums[i];
generate();
--depth;
used[i] = 0;
}
}
}
*total = 0;
generate();
free(used); free(temp);
return result;
}
N皇后布局
这是一个典型的约束满足问题，目标是在 n×n 棋盘上放置 n 个皇后使其互不攻击。主要难点在于检测当前位置是否与其他皇后冲突，包括同行、同列及两条对角线方向。
核心代码示意：
char*** solveNQueens(int n, int* num, int** lens) {
char*** results = malloc(1000 * sizeof(char**));
*lens = malloc(1000 * sizeof(int));
int* positions = malloc(n * sizeof(int)); // 存储每一行皇后的列位置
int placed = 0;
int valid(int row, int col) {
for (int r = 0; r < row; ++r) {
int c = positions[r];
if (c == col || abs(row - r) == abs(col - c))
return 0;
}
return 1;
}
void place(int row) {
if (row == n) {
results[*num] = malloc(n * sizeof(char*));
(*lens)[*num] = n;
for (int i = 0; i < n; ++i) {
results[*num][i] = malloc((n + 1) * sizeof(char));
for (int j = 0; j < n; ++j)
results[*num][i][j] = (positions[i] == j ? 'Q' : '.');
results[*num][i][n] = '\0';
}
(*num)++;
return;
}
for (int col = 0; col < n; ++col) {
if (valid(row, col)) {
positions[row] = col;
place(row + 1);
}
}
}
*num = 0;
place(0);
free(positions);
return results;
}
易犯错误提示
开发过程中常见失误包括忘记还原现场导致状态污染、边界条件设置不当引发访问越界、以及未能正确识别重复元素从而造成冗余计算等问题。此外还需特别留意一些细节，如判断对角线冲突时索引差值的绝对值比较方式等。
