C++怎么实现一个回溯算法_C++解决组合、排列、子集等搜索问题的通用框架

穿越時空 2025-11-21 00:00:00 次阅读

回溯算法是一种暴力搜索方法，通过递归尝试所有可能路径并在不满足条件时回退，避免无效计算。其核心是“做选择”和“撤销选择”，常用path记录当前路径，结合选择列表与剪枝优化效率。组合问题通过起始索引防止重复，排列问题用visited数组标记已使用元素，子集问题则每步选择是否加入当前元素。C++实现中借助递归函数维护状态，典型结构包括结束条件判断、循环中的选择与回溯恢复。掌握该模式可解决多数搜索类问题，关键在于理解状态的传递与还原机制。

回溯算法本质上是一种暴力搜索方法，适用于解决组合、排列、子集等搜索类问题。它通过递归尝试所有可能的路径，并在不满足条件时及时“回退”，从而避免无效计算。C++ 中实现回溯算法的关键在于状态维护与路径记录，下面给出一个通用框架和具体应用示例。

回溯算法基本结构

回溯的核心是“做选择”和“撤销选择”。其模板如下：

void backtrack(vector& path, 其他参数) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    for (选择 in 选择列表) {
        做选择：将选择加入 path;
        backtrack(path, 其他参数);
        撤销选择：从 path 移除该选择;
    }
}

关键点：

path：记录当前路径的选择序列
选择列表：根据题目限制动态变化
剪枝：在循环中提前跳过不可能的情况，提升效率

组合问题（如：从 n 个数中选 k 个）

要求无序且不重复，可用起始索引控制顺序，防止重复组合。

vector> combine(int n, int k) {
    vector> res;
    vector path;
    
    function backtrack = [&](int start) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            path.push_back(i);
            backtrack(i + 1);  // 下一轮从 i+1 开始，保证升序
            path.pop_back();
        }
    };
    
    backtrack(1);
    return res;
}

排列问题（如：全排列）

元素可按任意顺序出现，需用 visited 数组标记已使用元素。

vector> permute(vector& nums) {
    vector> res;
    vector path;
    vector used(nums.size(), false);
    
    function backtrack = [&]() {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            
            path.push_back(nums[i]);
            used[i] = true;
            backtrack();
            path.pop_back();
            used[i] = false;  // 回溯恢复状态
        }
    };
    
    backtrack();
    return res;
}

子集问题（每个元素选或不选）

每一步都可选择“加入”或“跳过”当前元素。

vector> subsets(vector& nums) {
    vector> res;
    vector path;
    
    function backtrack = [&](int start) {
        res.push_back(path);  // 每次进入都记录，包括空集
        
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtrack(i + 1);
            path.pop_back();
        }
    };
    
    backtrack(0);
    return res;
}

基本上就这些。掌握这个模式后，多数搜索类问题都可以套用类似结构，只需调整选择逻辑和剪枝条件即可。关键是理解递归过程中状态如何传递与还原。