当前位置：首页 > web >正文

回溯--一种暴力搜索算法

web 2025/7/3 20:08:55

一、组合问题-N个数里面按一定规则找出k个数的集合

（1）77. 组合 - 力扣

（2）216. 组合总和 III - 力扣

（3）39. 组合总和 - 力扣 --给出数组无重复，

（4）40. 组合总和 II - 力扣（LeetCode）--给出数组有重复

（5） 17. 电话号码的字母组合 - 力扣

二、子集问题- 一个N个数的集合里有多少符合条件的子集

（1） 78. 子集 - 力扣（LeetCode）

（2）90. 子集 II - 力扣（LeetCode）

三、排列问题-N个数按一定规则全排列，有几种排列方式

（1）842. 排列数字 - AcWing题库

（2）46. 全排列 - 力扣编辑

（3）47. 全排列 II - 力扣（LeetCode）

四、棋盘问题 -N皇后

（1）843. n-皇后问题 - AcWing题库

简单了解下回溯？

回溯是递归的副产品，只要有递归就会有回溯。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

什么是组合，什么是排列？

之前在dp（上）中遇到过求组合数/排列数的两种题型，组合是不强调元素顺序的，排列是强调元素顺序。例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。组合无序，排列有序。

如何理解回溯法？

回溯法解决的问题都可以抽象为树形结构，回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）----抽象成树来搜索就有点像dfs了哈哈哈【我感觉就是】

模版?

回溯三部曲：

①确认递归函数的返回值及参数

②确认回溯函数终止条件

③单层搜索的过程

vector<vector<int>> result; // 存放所有符合条件的路径
vector<int> path;           // 存放当前遍历路径void backtracking(参数) {if (终止条件) {result.push_back(path); // 保存结果return;}for (选择：当前节点的邻居节点) {path.push_back(选择);   // 处理节点backtracking(路径，选择列表)            // 递归path.pop_back();        // 回溯 撤销处理结果}
}

下面就是回溯算法的题目练习啦~~~

一、组合问题-N个数里面按一定规则找出k个数的集合

（1）77. 组合 - 力扣

写的时候会发现虽然想暴力搜索，但是用for循环嵌套连暴力都写不出来！！回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像for循环嵌套k层让人绝望。

抽象成树形结构：

n相当于树的宽度，k相当于树的深度，每次搜索到了叶子节点，我们就找到了一个结果。

回溯三部曲：

①函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数

然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）

②终止条件：

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。此时用result二维数组，把path保存起来，并终止本层递归

③单层搜索的过程：

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

class Solution {
public:vector<int> path;vector<vector<int>> res;void backtrac(int n,int k, int st){if(path.size()==k)res.push_back(path);return;else //dfs{for(int i=st;i<=n;i++){path.push_back(i);backtrac(n,k,i+1);path.pop_back();}}}vector<vector<int>> combine(int n, int k) {backtrac(n,k,1);return res;}};

（2）216. 组合总和 III - 力扣

本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合

using namespace std;class Solution {
public:vector<int> path; // 用于存储当前正在构建的组合vector<vector<int>> res; // 用于存储所有满足条件的组合vector<vector<int>> combinationSum3(int k, int n) {back(k, n, 1); // 调用回溯函数，从 1 开始枚举return res; // 返回结果}void back(int k, int n, int st) {// 如果当前组合的长度等于 k 且和为 n，将其添加到结果中if (path.size() == k && accumulate(path.begin(), path.end(), 0) == n) {res.push_back(path);return; // 返回，结束当前递归}// 从 st 开始枚举数字for (int i = st; i <= 9; i++) {path.push_back(i); // 将当前数字加入组合back(k, n, i + 1); // 递归枚举下一个数字path.pop_back(); // 回溯，移除当前数字}}
};

（3）39. 组合总和 - 力扣 --给出数组无重复，

在dp(上)写过求最终组合数的，题目一样，这道题要返回这些组合，也可以用dp

本题元素为可重复选取的。

如何重复选取呢，看代码，注释部分：

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates, target, 0, 0);return result;}
};

（4）40. 组合总和 II - 力扣（LeetCode）--给出数组有重复

本题数组candidates的元素是有重复的，本题元素为可不重复选取的，集合去重的重任就是used来完成的。

终止条件为 sum > target 和 sum == target
单层搜索：

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。

剪枝优化：

如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了，对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。


class Solution {
private:vector<vector<int>> result; // 存储所有符合条件的组合vector<int> path; // 存储当前路径（当前组合）// 回溯函数void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {// 如果当前路径的和等于目标值，将当前路径加入结果if (sum == target) {result.push_back(path);return;}// 遍历候选数组，从 startIndex 开始for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// 跳过重复的数字，避免生成重复组合if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}// 选择当前数字sum += candidates[i]; // 更新当前路径的和path.push_back(candidates[i]); // 将当前数字加入路径// 递归调用，继续选择数字backtracking(candidates, target, sum, i + 1);// 回溯：撤销选择sum -= candidates[i]; // 恢复当前路径的和path.pop_back(); // 移除当前数字}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {// 清空结果和路径result.clear();path.clear();// 对候选数组排序，方便剪枝和去重sort(candidates.begin(), candidates.end());// 开始回溯backtracking(candidates, target, 0, 0);// 返回结果return result;}
};

（5） 17. 电话号码的字母组合 - 力扣

class Solution {
public:// map存储数字到字母的映射map<int, string> mp = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"},{6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}};// 存储所有可能的字母组合vector<string> res;// 当前正在构建的字母组合string current;// 主函数：生成所有字母组合vector<string> letterCombinations(string digits) {// 如果输入为空，直接返回空结果if (digits.empty()) return res;// 开始递归生成组合back(digits, 0);// 返回所有生成的组合return res;}// 递归回溯函数void back(string digits, int index) {// 如果当前索引等于数字长度，说明已经生成了一个完整的组合if (index == digits.size()) {res.push_back(current); // 将当前组合添加到结果中return; // 返回，结束当前递归分支}// 获取当前数字对应的字母集合int digit = digits[index] - '0'; // 将字符转换为整数string letters = mp[digit]; // 获取对应的字母字符串// 遍历当前数字对应的每一个字母for (char letter : letters) {current.push_back(letter); // 将字母添加到当前组合中back(digits, index + 1); // 递归处理下一个数字current.pop_back(); // 回溯：移除最后一个字母，尝试下一个字母}}
};

，，，呜呜呜感觉好抽象

（）40. 组合总和 II - 力扣

与39 类似，只不过不允许重复

二、子集问题- 一个N个数的集合里有多少符合条件的子集

组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

（1） 78. 子集 - 力扣（LeetCode）

class Solution {
private:vector<vector<int>> result;vector<int> path;void dfs(vector<int>& nums, int st) {result.push_back(path); // 收集子集for (int i = st; i < nums.size(); i++) {path.push_back(nums[i]);dfs(nums, i + 1);//注意从i+1开始，元素不重复取path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return result;}
};

（2）90. 子集 II - 力扣（LeetCode）

这道题目和78.子集 (opens new window)区别就是集合里有重复元素了

回溯算法中的去重问题，在40.组合总和II (opens new window)中已经详细讲解过了，和本题是一个套路。

if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;

去重需要先对集合排序


class Solution {
private:vector<vector<int>> result;vector<int> path;void dfs(vector<int>& nums, int st,vector<bool>& used) {result.push_back(path); // 收集子集for (int i = st; i < nums.size(); i++) {//去重操作if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;path.push_back(nums[i]);used[i]=true;dfs(nums, i + 1,used);//注意从i+1开始，元素不重复取used[i]=false;path.pop_back();}}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());//去重需要先排序dfs(nums, 0,used);return result;}
};

三、排列问题-N个数按一定规则全排列，有几种排列方式

排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方

（1）842. 排列数字 - AcWing题库

用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。
用 state 数组表示数字是否用过。当 state[i] 为 1 时：i 已经被用过，state[i] 为 0 时，i 没有被用过。
dfs(i) 表示的含义是：在 path[i] 处填写数字，然后递归的在下一个位置填写数字。
回溯：第 i 个位置填写某个数字的所有情况都遍历后，第 i 个位置填写下一个数字。

#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{if(u > n)//数字填完了，输出{for(int i = 1; i <= n; i++)//输出方案cout << path[i] << " ";cout << endl;}for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n{if(!state[i])//如果数字 i 没有被用过{path[u] = i;//放入空位state[i] = 1;//数字被用，修改状态dfs(u + 1);//填下一个位state[i] = 0;//回溯，取出 i}}
}int main()
{cin >> n;dfs(1);
}

（2）46. 全排列 - 力扣

叶子节点，就是收割结果的地方。

那么什么时候，算是到达叶子节点呢？当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

// 此时说明找到了一组
if (path.size() == nums.size()) {result.push_back(path);return;
}

单层搜索的逻辑

for循环里不用startIndex了，因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素，直接跳过used[i] = true;path.push_back(nums[i]);dfs(nums, used);path.pop_back();used[i] = false;
}

最终代码

class Solution {
public:vector<vector<int>> res;vector<int> path;void dfs(vector<int> &nums,vector<bool>& used){//此时说明找到了一组if(path.size()==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i]==true) continue;//path里已经收录过，该层不能再有，直接跳过used[i]=true;path.push_back(nums[i]);dfs(nums,used);path.pop_back();used[i]=false;//下层还可以再用}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(),false);dfs(nums,used);return res;}
};

（3）47. 全排列 II - 力扣（LeetCode）

涉及到去重操作，去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。和组合总数II 类似思路

class Solution {
private:vector<vector<int>> result;vector<int> path;void dfs(vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {//去重的关键代码if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}if (used[i] == false) {used[i] = true;path.push_back(nums[i]);dfs(nums, used);path.pop_back();used[i] = false;}}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);dfs(nums, used);return result;}
};