回溯算法原理与实现——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、算法原理

1.1 算法定义

  在解决问题时，逐步构建解的过程中，如果发现当前选择无法得到有效解，就回溯（撤销上一步选择）并尝试其他可能的选择，直到找到可行解或遍历完所有可能。

  回溯算法可以形象地理解为 “走迷宫”：从起点出发，每次选择一条路径前进；如果遇到死胡同，就退回上一个岔路口，选择另一条路径继续探索，直到找到出口或确认没有出口。

1.2 关键特性

1. 试探性：每次选择都具有试探性，不确定当前选择是否能通向最优解；
2. 回溯性：当发现当前路径无法到达目标时，会撤销上一步操作，回到之前的状态；
3. 穷举性：理论上会遍历所有可能的解空间（但可通过剪枝优化减少无效探索）；
4. 递归性：通常采用递归实现，递归栈用于保存探索路径的状态；
5. 适用于组合优化问题：尤其适合求解排列、组合、子集、路径规划等具有多个解的问题。

1.3 核心思想

回溯算法的核心是深度优先搜索（DFS）+ 状态回退：

1. 从初始状态开始，选择第一个可能的选项；
2. 基于上一步的选择，继续选择下一个选项，逐步深入；
3. 若当前路径无法到达目标（或不符合约束条件），则撤销上一步选择（状态回退），尝试其他选项；
4. 重复步骤 2-3，直到找到可行解或遍历完所有可能。

二、实现步骤

回溯算法的典型实现步骤如下：

步骤 1：定义解空间

明确问题的所有可能解构成的集合。例如：

1. 排列问题中所有可能的元素排列

步骤 2：确定约束条件

定义判断当前选择是否有效的规则。例如：

1. 皇后问题中不能同行、同列、同对角线。

步骤 3：设计递归函数

1. 参数：包含当前状态（已选择的元素）、剩余可选元素等；
2. 终止条件：当已构建的解满足问题目标时，记录解并返回；
3. 递归逻辑：遍历所有可能的选择，筛选有效选择后递归探索，完成后回溯（撤销选择）；

步骤 4：剪枝优化

在递归过程中，提前排除不可能通向有效解的路径，减少探索次数。

三、优化思路

剪枝是提升回溯算法效率的关键，通过提前排除无效路径，减少递归次数。例如：

1. 在全排列问题中，used[i]的判断就是一种剪枝（排除已使用元素）；
2. 在 N 皇后问题中，可提前判断当前位置是否与已放置的皇后冲突，避免无效递归。

优化后的回溯算法时间复杂度通常低于暴力穷举，但最坏情况下仍可能达到指数级（如\(O(n!)\)）。

四、适用场景

回溯算法适用于求解具有多个可能解且需要穷举探索的问题，典型场景包括：

1. 排列组合问题（如全排列、子集生成、组合总和）；
2. 棋盘问题（如 N 皇后、数独求解）；
3. 路径搜索问题（如迷宫求解、图的所有路径）；
4. 约束满足问题（如八数码问题、着色问题）；
5. 组合优化问题（如旅行商问题的近似解）。

五、代码示例

下面以 “全排列问题” 为例，展示回溯算法的实现。

问题描述：给定一个不含重复数字的数组，返回其所有可能的全排列。

算法解析

1. 解空间：数组中所有元素的不同排列组合；
2. 约束条件：每个元素在排列中只能使用一次；
3. 回溯逻辑：
   • 用path记录当前构建的排列；
   • 用used数组标记元素是否已被选择；
   • 递归终止时，将path存入结果集；
   • 每次递归后通过pop_back()和used[i]=false撤销选择，实现回溯。

#include <iostream>
#include <vector>
#include <stack>
#include <tuple>

using namespace std;

//  递归实现全排列
// nums: 原始数组
// used: 记录元素是否已被使用
// path: 当前已选择的元素（部分解）
// result: 存储所有完整解
void backtrack_recu(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
    // 终止条件：当前路径长度等于数组长度（找到一个完整排列）
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }

    // 遍历所有可能的选择
    for (int i = 0; i < nums.size(); i++) {
        // 剪枝：跳过已使用的元素
        if (used[i]) continue;

        // 选择当前元素
        used[i] = true;
        path.push_back(nums[i]);

        // 递归探索下一层
        backtrack_recu(nums, used, path, result);

        // 回溯：撤销选择
        path.pop_back();
        used[i] = false;
    }
}

// 递归求解全排列的主函数
vector<vector<int>> permute_recu(vector<int>& nums) {
    vector<vector<int>> result;  // 存储所有排列结果
    vector<int> path;            // 记录当前路径
    vector<bool> used(nums.size(), false);  // 标记元素是否被使用
    backtrack_recu(nums, used, path, result);
    return result;
}

// 迭代实现全排列
vector<vector<int>> backtrack_iter(vector<int>& nums) {
    vector<vector<int>> result;
    if (nums.empty()) return result;

    // 栈中存储的状态：{当前路径, 使用标记数组, 当前遍历到的索引}
    // 作用：模拟递归调用栈，记录每一步的选择和上下文
    // 这里用元组(tuple)代替了结构体的定义
    stack<tuple<vector<int>, vector<bool>, int>> stk;
    
    // 初始化栈：空路径 + 全未使用标记 + 从索引0开始遍历
    stk.emplace(vector<int>(), vector<bool>(nums.size(), false), 0);

    while (!stk.empty()) {
        // 取出栈顶状态并弹出
        auto [path, used, idx] = stk.top();
        stk.pop();

        // 终止条件：路径长度等于数组长度 → 找到一个完整排列
        if (path.size() == nums.size()) {
            result.push_back(path);
            continue;
        }

        // 遍历所有可选元素（从idx开始，避免重复处理）
        for (int i = idx; i < nums.size(); i++) {
            // 剪枝：跳过已使用的元素
            if (used[i]) continue;

            // 1. 选择当前元素：生成新的路径和使用标记（避免修改原状态）
            vector<int> new_path = path;
            vector<bool> new_used = used;
            new_used[i] = true;
            new_path.push_back(nums[i]);

            // 2. 将「处理完当前元素后，下一层从0开始遍历」的状态入栈
            //    （对应递归中"递归探索下一层"的逻辑）
            stk.emplace(new_path, new_used, 0);

            // 3. 将「当前层继续遍历下一个元素」的状态入栈
            //    （对应递归中"for循环继续迭代"的逻辑）
            stk.emplace(path, used, i + 1);
            
            // 跳出循环：栈顶已存入后续状态，无需继续遍历（栈会处理后续i）
            break;
        }
    }

    return result;
}

// 迭代求解全排列的主函数
vector<vector<int>> permute_iter(vector<int>& nums) {
    vector<vector<int>> result;  // 存储所有排列结果
    result = backtrack_iter(nums);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = permute_iter(nums);

    // 输出所有排列
    cout << "全排列结果：" << endl;
    for (auto& perm : result) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}
        

输出结果

全排列结果：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
        

六、优缺点

优点

1. 逻辑清晰，代码模板化极强，所有问题都能套模板解决；
2. 能解决所有「组合 / 排列 / 子集」等搜索类问题，这些问题用循环无法解决（循环层数不确定）；
3. 可以通过剪枝优化，大幅提升效率。

缺点

1. 本质是暴力穷举，时间复杂度极高：最坏情况下是 O(2^n) 或 O(n!)（n 为元素个数），因为要遍历所有可能的路径；
2. 递归会占用栈空间，空间复杂度较高：空间复杂度主要由递归栈深度和路径数组决定，最坏是 O(n)。

七、算法对比

对比维度	回溯算法	贪心算法	分治算法	枚举算法
核心思想	试探 + 回退，带剪枝的 DFS 枚举	局部最优→全局最优	分而治之（分 + 治 + 合）	穷举解空间（遍历 + 验证）
决策方式	逐步试探决策，可撤销、可回退	一步一决策，无后效性	先拆分后合并，全局规划	逐一验证，无决策筛选
最优性保证	遍历所有有效路径，必找最优	仅满足特定条件时最优	解空间完整时必然最优
时间复杂度	较高 O(k×n!/2^n)	低（O (n)/O (n log n)）	较低（O (n log n)）	高（O (n²) 及以上）
空间复杂度	o(递归深度)	低（无需额外空间）	可能需要辅助空间	低（无需额外空间）
适用场景	求全解 / 约束多，需剪枝、可回退	资源分配、区间、图论	大规模可拆分问题	小规模解空间问题

八、总结

1. 回溯算法核心定义：回溯是基于穷举的暴力搜索算法，核心是「走不通就回头」，本质是树形结构的深度优先遍历。
2. 回溯三大核心要素：① 递归终止条件 ② 单层遍历的选择列表 ③ 做选择 → 递归 → 撤销选择
3. 回溯万能模板：背熟本文的 c++ 模板，所有回溯题都能套模板改写，只是「终止条件」和「选择列表」略有不同。
4. 核心优化手段：剪枝是回溯的灵魂，能提前排除无效路径，大幅提升效率，必须掌握。
5. 适用场景：组合、排列、子集、切割、棋盘问题，遇到这类题，优先用回溯算法解决！

返回顶部