【算法】小白也能懂 · 第 13 节：回溯算法

在前面的章节中，我们学习了递归、二分查找、排序、哈希表、图的遍历、二叉树、动态规划和贪心算法。今天，我们来认识一种和递归「亲如兄弟」的算法思想——回溯算法（Backtracking）。

回溯算法的核心理念是：一条路走到底，走不通就退回来，换一条路再试。它是解决「组合」「排列」「子集」等问题的万能钥匙。

1. 什么是回溯算法

1.1 一句话解释

回溯算法是一种穷举搜索策略。它通过递归的方式，系统地遍历所有可能的解空间，并在发现当前路径不可能产生有效解时，立即「回溯」（撤销上一步选择），尝试其他路径。

1.2 一个形象的类比

想象你在走一个迷宫：

1. 到了岔路口，随便选一条路走
2. 如果走到死胡同，退回到上一个岔路口
3. 换一条没走过的路继续走
4. 重复以上过程，直到找到出口或走遍所有路

这就是回溯——试错 + 撤销 + 换路。

1.3 回溯 vs 暴力枚举

回溯算法的效率优势来自于剪枝（Pruning）——在搜索过程中，如果发现当前分支不可能产生有效解，就直接跳过，不往下搜索。

2. 回溯算法的框架

回溯算法的代码结构非常统一，可以用一个模板来概括：

voidbacktrack(路径,选择列表){if(满足结束条件){收集当前结果;return;}for(选择:选择列表){做出选择;// 将选择加入路径backtrack(路径,选择列表);// 递归进入下一层撤销选择;// 回溯，恢复状态}}

三个关键步骤：

1. 做出选择：从选择列表中选一个元素，加入当前路径
2. 递归：带着这个选择，进入下一层搜索
3. 撤销选择：从当前路径中移除这个元素，恢复到选择前的状态

「撤销选择」是回溯的精髓——它让我们能够回到之前的状态，尝试其他可能性。

3. 经典例题 1：全排列

给定一个不含重复数字的数组，返回所有可能的全排列。
例如：输入 [1, 2, 3]，输出 [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

3.1 思路分析

全排列就是把数组中的数字重新排列，列出所有可能的顺序。我们可以这样思考：

• 第 1 个位置有 3 种选择（1、2、3）
• 第 2 个位置有 2 种选择（去掉已选的）
• 第 3 个位置有 1 种选择

3.2 代码实现

#include<iostream>#include<vector>usingnamespacestd;vector<vector<int>>result;vector<int>path;voidbacktrack(vector<int>&nums,vector<bool>&used){// 结束条件：路径长度等于数组长度if(path.size()==nums.size()){result.push_back(path);return;}for(inti=0;i<nums.size();i++){if(used[i])continue;// 跳过已使用的数字// 做选择path.push_back(nums[i]);used[i]=true;backtrack(nums,