C++回溯法框架解析与经典实例：全排列、子集与八皇后

回溯法的核心逻辑与通用框架

回溯法（Backtracking）本质上是在解空间树中寻找符合约束条件的解。其基本思想是：从根节点出发，沿深度优先搜索遍历解空间。在树的每个节点上，先判断是否满足约束条件（即“剪枝”），如果不满足则返回上一层继续尝试其他分支；如果满足，则继续深入探索直到找到完整解或确定无解为止。

一个标准的回溯过程通常包含以下步骤：

1. 初始化：定义解向量 $a=(a_1, a_2, ..., a_n)$，其中每个元素取自有限集合。
2. 扩展：在当前部分解基础上，尝试添加下一个可能的元素。
3. 检查：判断当前扩展后的解是否为完整解，以及是否符合约束条件。
4. 递归或回溯：若符合约束且未完成，递归进入下一层；若不符合或已完成但需寻找所有解，则撤销最后一步的选择，回到上一状态尝试其他可能性。

第1步：构建通用回溯骨架

无论具体问题是什么，回溯算法的代码结构高度相似。关键在于封装四个核心函数：isSolution（是否完成）、constructCandidate（生成候选项）、processSolution（处理结果）以及主控的 backTrack。

bool finished = false;

void backTrack(int input[], int inputSize, int index, int states[], int stateSize) {
    // 1. 判断是否已获得完整解
    if (isSolution(input, inputSize, index)) {
        processSolution(input, inputSize, index);
        return; // 若只需找一个解可在此标记finished=true并返回
    }

    // 2. 根据当前状态构造可行的候选项
    int candidates[MAXCANDIDATE];
    int ncandidates;
    constructCandidate(input, inputSize, index, candidates, &ncandidates);

    // 3. 遍历所有候选项，进行深度优先搜索
    for (int i = 0; i < ncandidates; i++) {
        states[index] = candidates[i]; // 做出选择
        backTrack(input, inputSize, index + 1, states, stateSize); // 递归
        
        if (finished) return; // 优化：已找到目标则停止搜索
    }
}

这个框架的精妙之处在于将“做什么”（处理解）与“怎么做”（生成候选、递归搜索）分离，使得切换不同问题时只需修改具体函数实现。

第2步：实例应用 - 字符串子集生成

子集问题要求从给定字符串中生成所有可能的字符组合。这是一个典型的二选一决策树：对于每个字符，只有“放入集合”或“不放入集合”两种状态。

以下代码展示了如何通过递归标志位 flag 来生成子集：

#include <iostream>
using namespace std;

char str[] = "abc";
const int size = 3;

// 构造候选：此处简单模拟两个选择 true 或 false
int constructCandidate(bool *flag, int size = 2) {
    flag[0] = true;
    flag[1] = false;
    return 2;
}

void printCombine(const char *str, bool *flag, int pos, int size) {
    if (str == NULL || flag == NULL || size <= 0) return;
    
    // 到达末尾，输出当前选择的子集
    if (pos == size) {
        cout << "{ ";
        for (int i = 0; i < size; i++) {
            if (flag[i]) cout << str[i] << " ";
        }
        cout << "}" << endl;
    } else {
        bool candidates[2];
        int number = constructCandidate(candidates);
        for (int j = 0; j < number; j++) {
            flag[pos] = candidates[j]; // 记录当前位的决策
            printCombine(str, flag, pos + 1, size); // 递归下一位
        }
    }
}

int main() {
    bool *flag = new bool[size];
    if (flag) printCombine(str, flag, 0, size);
    delete[] flag;
    return 0;
}

第3步：实例应用 - 字典序全排列

全排列问题相比子集更为复杂，因为每个位置的选择受之前位置的限制（不能重复）。我们需要维护一个 states 数组记录已选元素，并在构造候选项时过滤掉已使用的字符。

#include <iostream>
#include <cstring>
using namespace std;

char str[] = "abc";
const int size = 3;

// 构造候选项：排除已在 states 中使用过的字符
void constructCandidate(char *input, int inputSize, int index, 
                        char *states, char *candidates, int *ncandidates) {
    bool buff[256] = {false};
    for (int i = 0; i < index; i++) {
        buff[(unsigned char)states[i]] = true;
    }
    
    int count = 0;
    for (int i = 0; i < inputSize; i++) {
        if (!buff[(unsigned char)input[i]]) {
            candidates[count++] = input[i];
        }
    }
    *ncandidates = count;
}

bool isSolution(int index, int inputSize) {
    return index == inputSize;
}

void processSolution(char *states, int inputSize) {
    cout << states << endl;
}

void backTrack(char *input, int inputSize, int index, char *states, int stateSize) {
    if (isSolution(index, inputSize)) {
        processSolution(states, inputSize);
        return;
    }
    
    char candidates[100];
    int ncandidates;
    constructCandidate(input, inputSize, index, states, candidates, &ncandidates);
    
    for (int i = 0; i < ncandidates; i++) {
        states[index] = candidates[i];
        backTrack(input, inputSize, index + 1, states, stateSize);
    }
}

int main() {
    char *states = new char[size + 1];
    states[size] = '\0'; // 确保字符串结束符
    backTrack(str, size, 0, states, size);
    delete[] states;
    return 0;
}

此例的关键在于 constructCandidate 中对已选状态的监控，体现了回溯法中“约束检查”的重要性。

第4步：高难度实例 - N皇后问题（以8皇后为例）

八皇后问题是回溯法的经典应用场景。规则是8个皇后不能在同行、同列或同对角线。由于每行必然放一个皇后，我们只需关注每一行皇后所在的列号 states[row]。

• 冲突判断：新加入的皇后 $(index, i)$ 若与之前任意皇后 $(j, states[j])$ 满足 $|index - j| == |i - states[j]|$ （同对角线）或 $i == states[j]$ （同列），则该位置非法。

#include <iostream>
#include <cmath>
using namespace std;

int position[8]; // 输入源，这里仅为索引参考

// 构造候选：找出当前行所有不与前几行冲突的列号
void constructCandidate(int inputSize, int index, int *states, 
                        int *candidates, int *ncandidates) {
    *ncandidates = 0;
    for (int i = 0; i < inputSize; i++) {
        bool conflict = false;
        for (int j = 0; j < index; j++) {
            // 检查列冲突和对角线冲突
            if (i == states[j] || abs(index - j) == abs(i - states[j])) {
                conflict = true;
                break;
            }
        }
        if (!conflict) {
            candidates[(*ncandidates)++] = i;
        }
    }
}

void processSolution(int &count) {
    count++; // 找到一个合法布局，计数加1
}

void backTrack(int inputSize, int index, int *states, int stateSize, int &count) {
    if (index == inputSize) {
        processSolution(count);
        return;
    }
    
    int candidates[8];
    int ncandidates;
    constructCandidate(inputSize, index, states, candidates, &ncandidates);
    
    for (int i = 0; i < ncandidates; i++) {
        states[index] = candidates[i]; // 记录该行皇后的列位置
        backTrack(inputSize, index + 1, states, stateSize, count);
    }
}

int main() {
    int states[8];
    int count = 0;
    backTrack(8, 0, states, 8, count);
    cout << "Total solutions: " << count << endl;
    return 0;
}

总结

C++回溯法通过递归调用与状态回退（隐式栈）实现了穷举搜索的高效剪枝。掌握其通用模板，并根据具体问题设计 constructCandidate 中的约束逻辑，即可解决排列组合、路径规划等广泛问题。以上就是C++回溯法实例分析的详细内容，更多关于C++算法设计与优化的资料请关注本站其它相关文章！