1.什么是回溯算法?
回溯算法解题套路模板:
res = [] # 定义全局变量保存最终结果
state = [] # 定义状态变量保存当前状态
p,q,r # 定义条件变量(一般条件变量就是题目直接给的参数)
def back(状态,条件1,条件2,……):
if # 不满足合法条件(可以说是剪枝)
return
elif # 状态满足最终要求
res.append(state) # 加入结果
return
# 主要递归过程,一般是带有 循环体 或者 条件体
for # 满足执行条件
if # 满足执行条件
back(状态,条件1,条件2,……)
back(状态,条件1,条件2,……)
return res
public void backtrack(...){
if(是一个可行解) 将结果存入集合中;
if(无备选项或无须进一步搜索) return;
for(所有的备选项){
if(该备选项不满足约束) continue;
生成当前节点;
更新集合;
子问题backtrack();
//状态回退
删除节点;
回退集合;
}
}
实战出真知,下面请看例题: 例1: 46. 全排列
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums)
{
vector<vector<int>> ret;
vector<bool> used(nums.size(), false);
backTrack(nums, ret,new vector<int>,used);
return ret;
}
void backTrack(vector<int>& nums, vector<vector<int>>& ret, vector<int>* temp, vector<bool>& used)
{
//当temp数组存储元素个数等于size时,说明找到了一个解
if (temp->size() == nums.size())
{
ret.push_back(*temp);
}
else
{
//遍历所有可能子节点
for (int i = 0; i < nums.size(); i++)
{
//如果当前子节点已经被访问过,那么就跳过该子节点,访问下一个子节点
if (used[i]== true)
continue;
//设置当前没有访问过的子节点为访问过
used[i] = true;
//并加入temp数组
temp->push_back(nums[i]);
//temp的数组个数还不等于size,无法构成一个完整的解,因此需要通过递归找到剩余解
backTrack(nums,ret,temp, used);
//进行回退操作,将当前子节点的访问性改成未被访问过
used[i] = false;
//删除temp数组尾部元素,弹出当前子节点,因为当前子节点不符合规则
temp->pop_back();
}
}
}
};
void test()
{
Solution s;
vector<int> nums = { 1,2,3 };
vector<vector<int>> ret=s.permute(nums);
for (int i = 0; i < ret.size(); i++)
{
for (int j = 0; j < ret[0].size(); j++)
{
cout << ret[i][j] << " ";
}
cout << endl;
}
}
int main()
{
test();
system("pause");
return 0;
}
官方解法:
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
例2: 47. 全排列 II
相较于上一题全排列,这题最大的难点在于如何解决重复数字的排列问题。 如果继续采用上一题的解法,在输入为[1,1,2]的情况下,[2,1,1]这种结果会出现2次,显然不满足题目要求。 这里我们不妨回顾一下排列公式和组合公式。A(3,4) = 432,而C(3,4) = 432/(321),两者的唯一区别在于,组合去除了排列的顺序,即组合不在乎所选3个数字的具体选择顺序是怎么样的,只在乎我们具体选择了哪3个数字。 进一步,若给排列问题加上数字选择的顺序约束,即只能按照编号从小到大选择数字,其实质也将变为组合问题。 回到原问题,我们能否也去除数组中这两个1的顺序性,从而避免产生重复情况。类似的,我们将固定2个1的选择顺序,只能先选择第1个1,再选择第2个1,而不存在先选择第2个1,再选择第1个1的情况。 当然在调用回溯算法以前,我们需要先对数组进行排序,从而确保相同的数是相邻的。除此之外,和上一题的唯一差别仅在于选取备选项时要求固定顺序。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ret;
vector<bool> used(nums.size(), false);
vector<int> path;
sort(nums.begin(), nums.end());
backTrack(nums, ret,path,used);
return ret;
}
void backTrack(vector<int>& nums, vector<vector<int>>& ret, vector<int>& path, vector<bool>& used)
{
if (path.size() == nums.size())
{
ret.push_back(path);
return;
}
else
{
for (int i = 0; i < nums.size(); i++)
{
if (used[i] || (i>0&&nums[i] == nums[i-1] && !used[i-1]))
continue;
used[i] = true;
path.push_back(nums[i]);
backTrack(nums, ret, path, used);
used[i] = false;
path.pop_back();
}
}
}
};
例3: 39. 组合总和
注意:
这题同样存在如何避免重复结果的问题。类似的,为了变排列问题为组合问题,我们对数组的全部数字固定了选择顺序——下标小的数字必须在下标大的数字之前被选择。这里不再用到布尔数组used,原因是当我们固定了选择顺序后,在每一步,我们都容易知道,下标大于当前数字的是未被选择过的,而下标小于当前数字的是已经被选择过的。 不能再次选择之前选择过的数字,当选过第二个数字后,就不能选择第一个数字了
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
vector<vector<int>> ret;
vector<int> path;
backTrack(ret, target, path, candidates,0);
return ret;
}
//这里left作用:不能再次选择之前选择过的数字
void backTrack(vector<vector<int>>& ret, int target, vector<int>& path, vector<int>& cand, int left)
{
if (accumulate(path.begin(), path.end(), 0) == target)
{
ret.push_back(path);
return;
}
else if (accumulate(path.begin(), path.end(), 0) > target)
{
return;
}
else
{
for (int i = left; i < cand.size(); i++)
{
path.push_back(cand[i]);
backTrack(ret, target, path, cand, i);
path.pop_back();
}
}
}
};
例4:走迷宫
//迷宫 1为墙 0为通路
int Graph[][6] =
{
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1},
{1, 0, 1, 0, 0, 1},
{1, 0, 0, 0, 1 ,1},
{1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1}
};
出口:找到了迷宫出口 主体:从起点开始,不断往四周深入探索,直到遇到最终出口 返回:如果找到了一条通路或者进入思路,那么需要往后退一步,寻找其他可能解
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
//迷宫 1为墙 0为通路
int Graph[][6] =
{
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 1},
{1, 0, 1, 0, 0, 1},
{1, 0, 0, 0, 1 ,1},
{1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1}
};
//迷宫 起点 终点
void findPath(int(*Graph)[6], int x1, int y1, int x2, int y2)
{
//存放迷宫路径
static vector<pair<int,int>> path;
//找到出口
if (x1 == x2 && y1 == y2)
{
cout << "迷宫路径如下:" << endl;
path.push_back({ x1,y1 });
Graph[x1][y1] = -1;
for_each(path.begin(), path.end(), [](pair<int, int> path) {cout << "{" << path.first << "," << path.second << "}" << endl; });
return;
}
else
{
if (Graph[x1][y1]==0)//当前要走的方向为通路
{
int di = 0;//方向--右 下 左 上
int x, y;//记录下一次要走的方向
for (; di < 4; di++)
{
switch (di)
{
case 0://右---列加一
{
x = x1;
y = y1 + 1;
break;
}
case 1://下---行加一
{
x = x1 + 1;
y = y1;
break;
}
case 2://左---列减一
{
x = x1;
y = y1 - 1;
break;
}
case 3://上---行减一
{
x = x1 - 1;
y = y1;
break;
}
}
path.push_back({ x1,y1 });
Graph[x1][y1] = -1;
findPath(Graph, x, y, x2, y2);//更新寻找的起点
//回溯加剪枝
Graph[x1][y1] = 0;
path.pop_back();
}
}
}
}
int main()
{
findPath(Graph, 1, 1, 4, 4);
system("pause");
return 0;
}
总结: