1. 什么是回溯算法
回溯算法是一种经典的递归算法, 通常用于解决组合问题, 排列问题和搜索问题等,
回溯算法的基本思想 : 从一个初始状态开始, 按照一定的规则向前搜索, 当搜索到某个状态无法前进时, 回退到前一个状态, 再按照其他的规则搜索, 回溯算法在搜索过程中维护一个状态树, 通过遍历状态树来实现对所有可能解的搜索.
回溯算法的核心思想 : "试错", 即在过程中不断做出选择, 如果选择正确, 则继续向前搜索, 否则回退到上一个状态, 重新做出选择, 回溯算法通常用于解决具有多个解, 且每个解都需要搜索才能找到的问题.
2. 回溯算法模板
void backtrack(vector<int>& path, vector<int>& choice, ...) {
// 满⾜结束条件
if (/* 满⾜结束条件 */) {
// 将路径添加到结果集中
res.push_back(path);
return;
}
// 遍历所有选择
for (int i = 0; i < choices.size(); i++) {
// 做出选择
path.push_back(choices[i]);
// 做出当前选择后继续搜索
backtrack(path, choices);
// 撤销选择
path.pop_back();
}
}其中, path 表示当前已经做出的选择, choices 表示当前可以做的选择, 在回溯算法中, 我们需要做出选择, 然后递归调用回溯函数, 如果满足条件, 则将当前路径添加到结果集中, 否则, 我们需要撤销选择, 回到上一个状态, 然后继续搜索其他的选择.
回溯算法的时间复杂度通常较高, 因为它需要遍历所有可能的解, 但是, 回溯算法的空间复杂度较低, 因为它只要维护一个状态树, 在实际应用中, 回溯算法通常需要通过剪枝等方法进行优化, 以减少搜索的次数, 从而提高算法的效率.
3. 回溯算法的应用
1. 组合问题
组合问题是指从给定的一组数 (不重复) 中选取所有可能的 k 个数的组合. 例如, 给定数集 [1, 2, 3], 要求选取 k = 2 个数的所有组合.
结果为 :
[1, 2]
[1, 3]
[2, 3]
2. 排列问题
排列问题是指从给定的一组数 (不重复) 中选取所有可能的 k 个数的排列. 例如, 给定数集 [1, 2, 3], 要求选取 k = 2 个数的所有排列.
结果为 :
[1, 2]
[2, 1]
[1, 3]
[3, 1]
[2, 3]
[3, 2]
3. 子集问题
子集问题是指从给定的一组数中选取所有可能的子集, 其中每个子集中的元素可以按照任意顺序排列, 例如, 给定数集 [1, 2, 3], 要求选取所有可能的子集.
结果为 :
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]
总结 :
回溯算法是一种非常重要的算法, 可以解决许多组合问题, 排列问题和搜索问题, 回溯算法的核心思想是搜索状态树, 通过遍历状态树来实现对所有可能解的搜索, 回溯算法的模板非常简单, 但是实现起来需要注意一些细节, 比如如何做出选择, 如何撤销选择等.
示例一 : 全排列
OJ链接 : 全排列
算法思路 :
典型的回溯题目, 我们需要在每一个位置上考虑所有的可能情况并且不能出现重复, 通过深度优先搜索的方式, 不断地枚举每个数在当前位置的可能性, 并回溯到上一个状态, 直到枚举完所有可能性, 得到正确的结果.
每个数是否可以放入当前位置, 只需要判断这个数在之前是否出现即可. 具体地, 在这道题目中, 我们可以通过一个递归函数 backtrack 和标记数组 visited 来实现全排序.
递归函数设计 :
void backtrack(vector>& res, vector& nums, vector& visited, vector& ans, int step, int len)
参数: step (当前需要填入的位置), len (数组长度)
返回值 : 无
数组作用 : 查找所有合理的排列并存储在答案列表中
递归流程如下 :
1. 首先定义一个二维数组 res 用来存放所有可能的排列, 一个一维数组 ans 用来存放每个状态的排列, 一个一维数组 visited 标记元素, 然后从第一个位置开始进行递归
2. 在每个递归的状态中, 我们维护一个步数 step , 表示当前已经处理了几个数字
3. 递归结束条件 : 当 step 等于 nums 数组的长度时, 说明我们已经处理完了所有数字, 将当前数组存入结果中
4. 在每个递归状态中, 枚举所有下标i, 若这个下标未被标记, 则使用 nums 数组中当前下标的元素 :
a. 将 visited[i] 标记为 1;
b. ans 数组中第 step 个元素被 nums[i] 覆盖
c. 对第 step + 1 个位置进行递归
d. 将 visited[i] 重新赋值为 0, 表示回溯
5. 最后, 返回 res
特别地, 我们可以不使用标记数组, 直接遍历 step 之后地元素 (未被使用), 然后将其与需要递归地位置进行交换即可.
代码展示 :
class Solution {
vector<vector<int>> ret;
vector<int> path;
bool check[7];
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(path.size() == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(!check[i])
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
// 回溯 -> 恢复现场
path.pop_back();
check[i] = false;
}
}
}
};
示例二 : 子集
OJ链接 : 子集
算法思路 :
为了获得 nums 数组的所有子集, 我们需要对数组中的每个元素进行选择或不选择的操作, 即 nums 数组一定存在 2^(数组长度) 个子集, 对于查找子集, 具体可以定义一个数组, 来记录当前的状态, 并对其进行递归.
对于每个元素有两种选择 : 1. 不进行任何操作, 2. 将其添加至当前状态的集合, 在递归时我们需要保证递归结束时当前的状态与进行递归操作前的状态不变, 而当我们在选择进行步骤2进行递归时, 当前状态会发生变化, 因此我们需要在递归结束时撤回添加操作, 即进行回溯.
递归函数设计 : void dfs(vector>& res, vector& ans, vector& nums, int step)
参数 : step (当前需要处理的元素下标)
返回值 : 无
函数作用 : 查找集合的所有子集并存储在答案列表中
递归流程如下 :
1. 递归结束条件 : 如果当前需要处理的元素下标越界, 则记录当前状态并直接返回
2. 在递归过程中, 对于每个元素, 我们有两种选择
不选择当前元素, 直接递归到下一个元素
选择当前元素, 将其添加到数组末尾后递归到下一个元素, 然后在递归结束时撤回添加操作
3. 所有符合条件的状态都被记录下来, 返回即可
代码展示 :
解法一 :
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
ret.push_back(path);
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back();
}
}
};
- 回溯是一种递归算法，通过选择每个元素是否加入当前子集，递归地探索所有可能的组合。
- 每次递归时，都将当前的子集（即路径）存入结果集，并继续向后探索。探索完成后，通过回溯移除当前元素，恢复之前的状态，继续尝试其他可能的元素。
解法二 :
解法二就是进行选择, 可以选或者不选~
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if(nums.size() == pos)
{
ret.push_back(path);
return;
}
// 选
path.push_back(nums[pos]);
dfs(nums, pos + 1);
path.pop_back();
//不选
dfs(nums, pos + 1);
}
};
方法二递归次数多一些, 结果全是叶子节点, 而方法一递归次数少一些, 二叉树的节点全是结果~
