回溯算法和二叉树的递归（DFS） 算法非常类似，本质上就是一种暴力穷举算法。 它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当找到正确解的时候就将其记录，直到找到所有。
注意：回溯算法跟动态规划一样，都是一种穷举的方式，但是不一样的是，动态规划一般是求最值（最优解），而回溯算法一般是求所有的可行解而非最值。
回溯算法的核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」。
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return //这也是一种回退
for 选择 in 选择列表:
做选择（尝试做这个选择）：前序位置
backtrack(路径, 选择列表)
撤销选择（退回到之前状态）：后序位置
下面框架更清晰些：
//state 表示问题的当前状态（或者说路径），choices 表示当前状态下可以做出的选择
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &results)
{
// 判断是否为解（也就是回溯终止的条件～）
if (isSolution(state))
{
recordSolution(state, results); // 记录解
return;// 不再继续搜索
}
// 遍历所有选择
for (Choice choice : choices)
{
// (如有)剪枝:判断选择是否合法
if (isValid(state, choice))
{
// 尝试:做出选择，更新状态 （将选择列表放入当前状态或者路径中）
makeChoice(state, choice);
backtrack(state, choices, res);
// 回退:撤销选择，恢复到之前的状态 （将上面放入的选择从当前状态或者路径中拿掉）
undoChoice(state, choice);
}
}
}
N 皇后问题
时间复杂度是O（N！）回溯算法中对应着For循环。空间复杂度：O(N)是递归栈，但是还有O（N2）是存放的结果占用的空间
// 本题本质上就是，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后
class Solution {
public:
// 输入棋盘边长 n，返回所有合法的放置
vector<vector<string>> solveNQueens(int n) {
// 每个字符串代表一行，字符串列表代表一个棋盘
// '.' 表示空，'Q' 表示皇后，初始化空棋盘
vector<string> board(n, string(n, '.'));//将其初始化为空棋盘
// 注意,对于board为n个string,每个string为n个字符
vector<vector<string>> result;//结果(存放的所有结果)
backtrack(board,result, 0);//一开始row为0
return result;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, vector<vector<string>>& result, int row)
{
//结束的条件
if(row==board.size())
{
result.push_back(board);//将当前的结果存放
}
//对于当前row的每一列
for (int col = 0; col < board[0].size(); col++)
{
//先判断是否合法(也就是说是否可以在board[row][col]上放置皇后)
if (!isValid(board, row, col))
{
continue;//若无效,那么就是当前位置不应该方
}
board[row][col]='Q';// 做选择
backtrack(board,result, row+1);//回溯算法(一行一行的放，故此下面只需要检查列不用检查行)
board[row][col]='.';// 撤销选择
}
}
// 判断是否可以在 board[row][col] 放置皇后
//因为皇后是一行一行从上往下放的，所以左下方，右下方和正下方不用检查（还没放皇后）；
//因为一行只会放一个皇后，所以每行不用检查。也就是最后只用检查上面，左上，右上三个方向。
bool isValid(vector<string>& board, int row, int col)
{
//先检查在这一行前,当前列是否有皇后放置了（固定了列，行变，就是一列）
for(int i=0;i<row;i++)
{
if (board[i][col]=='Q')//存在皇后
return false;
}
// 检查右上方.右上方就是当前row-1,col+1
for(int i=row-1, j=col+1; i>=0 && j<board.size(); i--, j++)
{
if (board[i][j]=='Q')//存在皇后
return false;
}
//检查左上方.右上方就是当前row-1,col-1
for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)
{
if (board[i][j]=='Q')//存在皇后
return false;
}
return true;//都不满足则是true
}
};
解法跟上面是一样的，只是保存结果不一样而已~当然直接返回result.size()也可以，但是在某些测试下可能会内存超出限制，为此还是应该把返回的结果为int
class Solution {
public:
// 输入棋盘边长 n，返回所有合法的放置
int totalNQueens(int n) {
// 每个字符串代表一行，字符串列表代表一个棋盘
// '.' 表示空，'Q' 表示皇后，初始化空棋盘
vector<string> board(n, string(n, '.'));//将其初始化为空棋盘
// 注意,对于board为n个string,每个string为n个字符
int result=0;//结果
backtrack(board,result, 0);//一开始row为0
return result;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, int& result, int row)
{
//结束的条件
if(row==board.size())
{
result+=1;//结果+1
}
//对于当前row的每一列
for (int col = 0; col < board.size(); col++)
{
//先判断是否合法(也就是说是否可以在board[row][col]上放置皇后)
if (!isValid(board, row, col))
{
continue;//若无效,那么就是当前位置不应该方
}
board[row][col]='Q';// 做选择
backtrack(board,result, row+1);//回溯算法
board[row][col]='.';// 撤销选择
}
}
// 判断是否可以在 board[row][col] 放置皇后
bool isValid(vector<string>& board, int row, int col)
{
//先检查在这一行前,当前列是否有皇后放置了
for(int i=0;i<row;i++)
{
if (board[i][col]=='Q')//存在皇后
return false;
}
// 检查右上方.右上方就是当前row-1,col+1
for(int i=row-1, j=col+1; i>=0 && j<board.size(); i--, j++)
{
if (board[i][j]=='Q')//存在皇后
return false;
}
//检查左上方.右上方就是当前row-1,col-1
for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--)
{
if (board[i][j]=='Q')//存在皇后
return false;
}
return true;//都不满足则是true
}
};
排列/组合/子集问题
1.子集（元素无重不可复选）
时间复杂度为O(N*2N),空间复杂度为O（N）
class Solution {
public:
// 定义回溯算法
void backtrack(vector<int>& nums, vector<int>& track, vector<vector<int>>& result, int index)
{
// 没有终止条件，每次应该就是把当前的track放入result中
result.push_back(track);//放入结果
for(int i=index;i<nums.size();i++)
{
// 前序的位置
track.push_back(nums[i]);//放入
// 回溯函数调用(这里index+1，表示不允许重复使用当前数字)
backtrack(nums, track, result, i+1);//注意是i+1
// 后序的位置
track.pop_back();// 拿出来最后一个
}
}
vector<vector<int>> subsets(vector<int>& nums) {
// 注意：解集不能包含重复的子集。也就是不考虑顺序
vector<vector<int>> result;//最终的结果
vector<int> track;//每次结果
backtrack(nums, track, result, 0);
return result;
}
};
2.组合（元素无重不可复选）
与上一题的解题思路几乎一样
class Solution {
public:
void backtrack(const int n, const int k, vector<vector<int>>& results, vector<int>& each_result, int index)
{
// 结束条件,当size为k时
if(each_result.size()==k)
{
results.push_back(each_result);
}
// 遍历整个数组
for(int i=index; i<=n;i++)//注意时闭区间,包含了n
{
// 前序位置
each_result.push_back(i);
// 回溯
backtrack(n,k,results,each_result,i+1);//i的下一个
//后序位置
each_result.pop_back();//插入的用完后删掉
}
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> results;
vector<int> each_result;
backtrack(n,k,results,each_result,1);//index为索引到的数字,从1开始
return results;
}
};
组合总和III
注意要从1开始
class Solution {
public:
void backtrack(const int num, int target, vector<int>& each_path, vector<vector<int>>& results, int index)
{
//递归终止条件
if(each_path.size()==num)//达到数目了
{
if(target==0)//减到0了
results.push_back(each_path);
return;
}
//选择列表
for(int i=index;i<=9;i++)//从index开始，那么就避免了排列的情况（仅仅是组合）
{
if(target-i<0)//进行剪枝
continue;
// 做选择
each_path.push_back(i);
target-=i;
backtrack(num,target,each_path,results,i+1);//下次是o的下一个
//撤销选择
each_path.pop_back();
target+=i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
//首先由于每个数最多使用一次，因此是无重不可复选
vector<int> each_path;
vector<vector<int>> results;
backtrack(k,n,each_path,results,1);//注意从1开始
return results;
}
};
分割回文串
本质上为子集问题。可重不可复选，只是额外需要判断是否回文子串（用于剪纸）
class Solution {
public:
//双指针法判断当前字符串是否为回文子串
bool function(string s, int left, int right)
{
//确保不越界以及相等
while(left<right)
{
if(s[left]!=s[right])
return false;//返回不是回文串
left++;
right--;
}
//注意没有两者相等的情况，这样可以处理aba以及aa所有情况
return true;
}
void backtrack(string s, vector<string> each_path, vector<vector<string>>& results, int index)
{
//递归终止条件
if(index==s.size())
{
results.push_back(each_path);
return;
}
//选择列表
for(int i=index;i<s.size();i++)//子集形式
{
//先判断是否回文子串（相当于剪枝）
if(function(s,index, i))//注意：i为当前右指针的位置
{
// 若是回文子串
int left=index;
int right=i;
string cur_str=s.substr(left,right-left+1);
//做选择
each_path.push_back(cur_str);
//回溯调用
backtrack(s,each_path,results,i+1);//下次用i+1开始
// 撤销选择
each_path.pop_back();
}
else
continue;//当前跳过
}
}
vector<vector<string>> partition(string s) {
//相当于可重不可复选
//且为子集
vector<vector<string>> results;
vector<string> each_path;
backtrack(s,each_path,results,0);//从第一个字符开始
return results;
}
};
复原IP地址
跟上一题分割回文子串很像，只是额外多了要添加点的操作。
关键点在于额外构建函数每次判断字符是否合法的一位。合法就放入，然后继续回溯计算。下一次重新测[index，i]区间
class Solution {
public:
//额外定义一个函数判断某个字符是否合法的ip
bool isvail(string s, int start, int end)
{
if(start>end)
return false;
if(end-start+1>4)//长度超过了4
return false;
if(s[start]=='0' && start!=end)//也就是不是一个0，存在前导0
return false;
string cur_str=s.substr(start,end-start+1);//注意是左右闭区间，因此要+1
int str_int=stoi(cur_str);
if(str_int>255)//超过255
return false;
return true;//通过所有测试，为对
}
void backtrack(string s, vector<string> each_path,vector<string>& results, int index)
{
//递归终止的条件
if(index==s.size())
{
if(each_path.size()==4)//刚刚好为4
{
string cur_str;//插入点
for(int i=0;i<each_path.size();i++)
{
cur_str+=each_path[i]+'.';
}
results.push_back(cur_str.substr(0,cur_str.size()-1));//最后一个点不要
}
return;
}
//选择列表
for(int i=index;i<s.size();i++)
{
if(isvail(s, index,i))//先判断这个区间是否有效
{ //有效才处理
//做选择
each_path.push_back(s.substr(index,i-index+1));
//回溯
backtrack(s, each_path, results,i+1);
//撤销选择
each_path.pop_back();
}
}
}
vector<string> restoreIpAddresses(string s) {
// 首先只包含数字
// 不能 重新排序或删除 s 中的任何数字
// 因此相当于子集
// 可重不可复选
vector<string> each_path;
vector<string> results;
backtrack(s, each_path, results,0);
return results;
}
};
3.排列（元素无重不可复选）
注意：此题的全排列问题不包含重复的数字，下一题则是包含重复数字。递归的时间复杂度为O（N！）加上递归中每个有for循环，故此应该是O（N*N！）。空间复杂度应该是O（N）
class Solution {
public:
void calculate(vector<int>& num, int index, vector<vector<int>> &results)
{
//遍历完了，退出
if(index==num.size()-1) //当index等于最后一个字节时，把对调后的num放入结果中(是否减1结果一样～)
{
results.push_back(num);
return;
}
// index可以理解为一直递增，避免重复使用
for(int i=index;i<num.size();i++)
{
//做选择
swap(num[i],num[index]);//变换num中两个索引的顺序，只是采用swap代替了path数组，少了一个中间变量
calculate(num, index+1, results);//下一次计算，注意是index+1。
//撤销选择
swap(num[index],num[i]);//变回去（变完后要变回去，才可以确保下次变是正确的）
}
}
vector<vector<int>> permute(vector<int>& nums) {
//采用递归的方法时间复杂度为O（N！）
vector<vector<int>> results;
calculate(nums,0, results);
return results;
}
};
下面代码跟上面的区别只是上面通过索引index以及swap来保证交互的两个不会重复被用，此处用vector
class Solution {
public:
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path,vector<vector<int>>& results)
{
//回溯回调的终止条件
if(path.size()==nums.size())//全部用完了
{
results.push_back(path);
return;
}
for(int i=0;i<nums.size();i++)//从列表中选择
{
//根据是否用过来剪枝
if(used[i]==true)
continue;//若当前已经被用过了。就剪枝
//前序位置做选择
path.push_back(nums[i]);
used[i]=true;//标记用过
backtrack(nums, used, path,results);
//后序位置撤销选择
path.pop_back();
used[i]=false;//撤销标记
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(),false);//用于标记当前元素是否被使用过
vector<vector<int>> results;//记录所有的结果
vector<int> path;//记录每次的结果
backtrack(nums, used, path,results);
return results;
}
};
4.子集（元素可重不可复选）
通过新增的if判据，来实现元素虽然存在重复,但是最终结果不能管顺序。空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。 而时间复杂度。首先sort排序的时间复杂度为：O（N）回溯的时间复杂度为O(2N),然后遍历每个字符，所以应该是O（N2N）至于前面排序sort的时间复杂度也是O（N），因此总的时间复杂度为O（N2N）
class Solution {
public:
void backtrack(vector<int>& nums, vector<vector<int>>& results, vector<int>& each_result, int index)
{
//没有结束条件,每次直接返回
results.push_back(each_result);
//遍历每个字符
for(int i=index;i<nums.size();i++)
{
// 注意要对i>index才执行 ( 剪枝逻辑，值相同的相邻树枝，只遍历第一条)
if(i>index && nums[i-1]==nums[i])//若当前跟上一个一样,那么就不执行
continue;//不执行
//前序位置
each_result.push_back(nums[i]);
// 回溯前,先if判断当前结果是否出现过
// if(find(results.begin(),results.end(),each_result)==results.end())//若找不到(这样做不行)
backtrack(nums, results,each_result,i+1);
//后序位置,放入后删掉
each_result.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
// 元素虽然存在重复,但是最终结果不能管顺序
sort(nums.begin(),nums.end());//排序一下
vector<vector<int>> results;
vector<int> each_result;
backtrack(nums, results,each_result,0);//索引从0开始
return results;
}
};
非递减子序列
相当于取有序的子集（可重，不可复选）。但是跟上一题不一样的是不能对原数组进行排序的，因此其原本的去重的方式不适用。此处改为用find来看是否存在重复的结果。
class Solution {
public:
void backtrack(vector<int> nums, vector<int> each_patch, vector<vector<int>>& results, int index)
{
//递归终止条件
if(index==nums.size())
{
if(each_patch.size()>1)//必须大于1
if(find(results.begin(),results.end(),each_patch)==results.end())//找到了
results.push_back(each_patch);
return;
}
if(each_patch.size()>1)//大于1已经可以放置了
{
if(find(results.begin(),results.end(),each_patch)==results.end())//找不到才放
results.push_back(each_patch);
}
//选择列表
for(int i=index;i<nums.size();i++)
{
if(!each_patch.empty())//若不为空，且最后一个大于当前，就剪枝，不能放
{
if(each_patch[each_patch.size()-1]>nums[i])
continue;
}
//做选择
each_patch.push_back(nums[i]);
backtrack(nums,each_patch,results,i+1);
//撤销选择
each_patch.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
//相当于取有序的子集（可重，不可复选）
//但是跟90.子集III不一样的是不能对原数组进行排序的，因此其原本的去重的方式不适用
// 注意从样例中可以看到不能改变原本的数组排列顺序
vector<vector<int>> results;
vector<int> each_patch;
backtrack(nums,each_patch,results,0);
return results;
}
};
另外一种解法，额外维护一个数组来标记是否重复，但注意是标记每一层（宽度）而非深度！！！
class Solution {
public:
void backtrack(vector<int> nums, vector<int> each_patch, vector<vector<int>>& results, int index)
{
//递归终止条件
if(index==nums.size())
{
if(each_patch.size()>1)//必须大于1
results.push_back(each_patch);
return;
}
if(each_patch.size()>1)//大于1已经可以放置了
{
results.push_back(each_patch);
}
//选择列表
unordered_set<int> used;//用于记录这个元素在本层是否用过
for(int i=index;i<nums.size();i++)
{
if(used.find(nums[i])!=used.end())//被用过了
continue;
if(!each_patch.empty())//若不为空，且最后一个大于当前，就剪枝，不能放
{
if(each_patch[each_patch.size()-1]>nums[i])
continue;
}
//做选择
each_patch.push_back(nums[i]);
used.insert(nums[i]); // 记录这个元素在本层用过了，本层后面不能再用了
backtrack(nums,each_patch,results,i+1);
//撤销选择
each_patch.pop_back();
//不需要撤销used，因为是用于记录是否重复！
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
//相当于取有序的子集（可重，不可复选）
//但是跟90.子集III不一样的是不能对原数组进行排序的，因此其原本的去重的方式不适用
// 注意从样例中可以看到不能改变原本的数组排列顺序
vector<vector<int>> results;
vector<int> each_patch;
backtrack(nums,each_patch,results,0);
return results;
}
};
5.组合（元素可重不可复选）
组合跟子集问题时很类似的，故此解法基本一样~注意对于剩余target值的管理。等于0时返回，小于0时没必要继续计算，否则浪费计算时间~
class Solution {
public:
void backtrack(vector<int>& candidates, int target, vector<vector<int>>& results,vector<int>& each_result, int index)
{
// 定义结束标致,当target为0时
if(target==0)
{
results.push_back(each_result);
return;
}
// 遍历整个数组
for(int i=index;i<candidates.size(); i++)
{
// 满足条件进行剪枝,以此去重
if(i>index && candidates[i]==candidates[i-1])//若当前值等于上一个值.同时除掉最开始的index以保证每次选重复值的第一个
continue;
if(target-candidates[i]<0)//超出了(再继续计算已经没有意义了)
return; //或者break
//前序
each_result.push_back(candidates[i]);
backtrack(candidates, target-candidates[i],results,each_result,i+1);//注意不要漏掉每次减candidates[i]
each_result.pop_back();//后序的位置上删掉
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 存在重复的数字,但不能包含重复的组合(顺序变化不算)
//先进行排序,这样有利于去重
sort(candidates.begin(),candidates.end());
vector<vector<int>> results;
vector<int> each_result;
backtrack(candidates, target,results,each_result,0);
return results;
}
};
6.排列（元素可重不可复选）
class Solution {
public:
void backtrack(vector<int>& nums, vector<int>& path, vector<vector<int>>& results, vector<bool>& used)
{
// 回溯终止的条件，当当前存满了，就放入results
if(path.size()==nums.size())
{
results.push_back(path);
return;
}
for(int i=0;i<nums.size();i++)
{
if(used[i]==true)
continue;//用过了
if(i>0 && nums[i]==nums[i-1] && used[i-1]==false)//跟上一个相同，那么结果会一样，也剪枝。注意额外的约束是used[i-1]==false
continue;// 如果前面的相邻相等元素没有用过，则跳过。如果用了就是当前轮再次添加而已～
// if(i>0 && nums[i]==nums[i-1] && used[i-1]==true)//这也可以通过，只是测试更久一些，注意：上一个是否用过来决定当前是否跳过
// continue;
//做选择
used[i]=true;
path.push_back(nums[i]);
backtrack(nums, path,results,used);
// 撤销选择
used[i]=false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> results;
vector<int> path;
vector<bool> used(nums.size(),false);
sort(nums.begin(),nums.end());//排序。 让相同的元素靠在一起
backtrack(nums, path,results,used);
return results;
}
};
也有一种情况是只需要输出一共的排列的数的，但用results数组的size会导致内存不够，为此用int来代替~
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void backtrack(vector<char>& group, vector<char>& path, int& results, vector<bool>& used)
{
// 回溯的终止条件~
if(path.size() == group.size())
{
results++;
return;
}
// 可以选择的列表
for(int i = 0; i < group.size(); i++)
{
if(used[i]==true)//判断是否被用过
{
continue;
}
// 剪枝避开重复的元素
if(i > 0 && group[i] == group[i - 1] && used[i - 1]==false)
{
continue;
}
// 做选择
path.push_back(group[i]);
used[i] = true;
backtrack(group, path, results, used);
// 撤销选择
path.pop_back();
used[i] = false;
}
}
int main()
{
//输入只包含大写字母的字符串S
string S;
cin >> S;
vector<char> group;
for(auto c : S)
{
group.push_back(c);
}
sort(group.begin(),group.end());
// 采用回溯算法
vector<char> path;//
//vector<vector<char>> results;
int results=0;
vector<bool> used(group.size(), false);//是否使用过
backtrack(group, path, results, used);
//把结果输出
std::cout<<results;
return 0;
}
此题与上面1中的第46题不同的是包含了重复的字母，因此全排列可能包含重复的序列，故此需要去重。其余的解题思路跟上面是一样的
class Solution {
public:
void calculate(vector<int>& nums, vector<vector<int>> &result, int first_index, const int len)
{
if(first_index==len-1)//到达了尾部
{
result.push_back(nums);
return;
}
set<int> flag;//用于记录每次是否遍历过（在set中每个元素的值都唯一，因此可以判定当前这个数字有没有出现过！）
for(int i=first_index;i<len;i++)
{
//满足某些情况下，跳过不处理
if(
flag.find(nums[i])!=flag.end()//如果找到一样的
)
continue;//就不处理了，跳过
flag.insert(nums[i]);//每次插入新的
swap(nums[i], nums[first_index]);//调换位置
calculate(nums, result, first_index+1,len); // first_index可以理解为固定不变的位置，变的i为与其兑换进行全排列
swap(nums[i], nums[first_index]);//换回来，继续下次
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
calculate(nums, result, 0, nums.size());
return result;
}
};
7.组合（元素无重可复选）
原本采用递归的解法
class Solution {
public:
void calculate(vector<vector<int>>& result_group,vector<int>& candidates, int target, vector<int>& temp, int index)
{
if(index==candidates.size())
return;//最后一个了，跳出
if(target==0)//找到了(放入结果并退出)
{
result_group.push_back(temp);
return;
}
calculate(result_group,candidates,target,temp,index+1);//遍历每一个index
// 同一个index下，遍历计算(会通过上面的更新)
if(target-candidates[index]>=0)//大于0，可以继续计算
{
temp.push_back(candidates[index]);
calculate(result_group,candidates,target-candidates[index],temp,index);
temp.pop_back();//当前计算完就删掉
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//没有重复的数组,可以重复选择
vector<vector<int>> result_group;
vector<int> temp;
// 不同于两数之和或三数之和，数目可以是随意的。
// 采用递归的解法，对于选择了第i位，target=target-candidates[i],继续从candidates中找，直到target=0
calculate(result_group,candidates,target,temp,0);
return result_group;
}
};
上面方法的思路是可以实现的，但是不成体系，为此用回溯的框架看看
class Solution {
public:
void backtrack(vector<vector<int>>& results,vector<int>& candidates, int target, vector<int>& each_result, int index)
{
// 定义结束条件
if(target==0)//找到了(放入结果并退出)
{
results.push_back(each_result);
return;
}
for(int i=index;i<candidates.size();i++)
{
if(target-candidates[i]<0)//接下来就无法算了,为此跳过这个节点
continue;
each_result.push_back(candidates[i]);//前序
// 由于可以多次选择,因此无需+1,每次都重新看
backtrack(results,candidates,target-candidates[i],each_result,i);//无需i+1，那么当前的就可以被再次选择
each_result.pop_back();//后序
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
//没有重复的数组,可以重复选择
vector<vector<int>> results;
vector<int> each_result;
backtrack(results,candidates,target,each_result,0);
return results;
}
};
8.子集（元素无重可复选）
此类型目前还没找到例题
9.排列（元素无重可复选）
此类型目前还没找到例题
10.元素可重可复选
元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？ 因此可以先对元素进行去重处理，然后就是退化为无重可复选的情况了。
有限制的回溯算法：火车进站
有两种选择的回溯算法，或者说有限制的回溯算法
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
void backtrack(vector<int>& input_group, stack<int>& path, vector<int>& each_result, vector<vector<int>>& results, int index)
{
//若栈为空,且所有车都进站了为终止条件
if(index==input_group.size() && path.empty())
{
results.push_back(each_result);//把出站的方案记录
return;
}
//火车还可以进栈
if(index<=input_group.size()-1)
{
//执行选择1:将火车开入栈
path.push(input_group[index]);
backtrack(input_group,path,each_result,results,index+1);//一辆车进入栈了，因此index要递增
//撤销选择，就是出栈（此处不需要记录）
path.pop();
}
//若有火车可以先出栈
if(!path.empty())
{
//执行选择2:将火车开出栈
each_result.push_back(path.top());//记录出栈的结果
path.pop();//出栈
backtrack(input_group,path,each_result,results,index);//回溯调用
//撤销出栈的选择
path.push(each_result.back());//把结果放回去（也就是此时each_result中最新的一个）
each_result.pop_back();
}
}
int main() {
int N;
cin>>N;//一共的火车数
vector<int> input_group;
int temp;
for(int i=0;i<N;i++)
{
cin>>temp;
input_group.push_back(temp);
}
//只需要输出出站的方案，且为全部，因此用回溯算法
stack<int> path;
vector<vector<int>> results;
vector<int> each_result;
backtrack(input_group,path,each_result,results,0);
sort(results.begin(),results.end());
for(int i=0;i<results.size();i++)
{
auto temp= results[i];
for(int j=0;j<temp.size();j++)
{
std::cout<<temp[j]<<" ";
}
std::cout<<std::endl;
}
}
有限制/有选择的回溯算法：括号生成
对于括号合法性的判断，主要是借助「栈」(详情请见博客Link)，而对于括号的生成，一般都要利用回溯算法 进行暴力穷举。
关键的解题点或者说约束点在于：对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量
class Solution {
public:
void back(int n, int num_left, int num_right, string& path, vector<string>& result)
{
//回溯终止条件
if(num_left==num_right && num_left==n)
{
result.push_back(path);
return;
}
//选择1:放入左括号
if(num_left<n)//可以放入左括号
{
// 选择
path.push_back('(');
num_left++;
back(n, num_left, num_right, path, result);
//撤销选择
path.pop_back();
num_left--;
}
// 选择2:放入右括号
if(num_right<n)//可以放入右括号
{
if(num_left>num_right)//才是真正可以放入右括号。放完之后，num_left>=num_right
{
path.push_back(')');
num_right++;
back(n, num_left, num_right, path, result);
//撤销选择
num_right--;
path.pop_back();
}
}
}
vector<string> generateParenthesis(int n) {
// 1、一个「合法」括号组合的左括号数量一定等于右括号数量。
// 2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
string path;
vector<string> results;
int num_left=0,num_right=0;
back(n, num_left, num_right, path, results);
return results;
}
};
解数独
这个回溯算法需要带return bool的，一找到结果马上停止进一步搜索。
class Solution {
public:
bool vailed_function(vector<vector<char>>& board, int i, int j, char value)
{
for (int n = 0; n < 9; n++) {
// 判断行是否存在重复
if (board[i][n] == value) return false;
// 判断列是否存在重复
if (board[n][j] == value) return false;
// // 判断 3 x 3 方框是否存在重复
// if (board[(i/3)*3 + n/3][(j/3)*3 + n%3] == value)
// return false;
}
// // //查看矩阵范围(以3为一个大格)
for(int x=(i/3)*3;x<(i/3+1)*3;x++)//整除3
{
for(int y=(j/3)*3;y<(j/3+1)*3;y++)
{
if(board[x][y]==value)
return false;
}
}
return true;//上面都通过了就是true
}
//此回溯需要有返回值
bool backtrack(vector<vector<char>>& board, int i, int j)
{
//回溯的终止条件：到达了边缘
if(i==board.size())//注意i=9是越界了～
{
return true;//填完了～
}
//按照列索引
if(j==board[0].size())//当前列满了
{
return backtrack(board,i+1,0);//j回0
}
// 如果有预设数字，不用我们穷举（不要漏了）
if (board[i][j] != '.') {
return backtrack(board, i, j + 1);
}
//遍历选择列表（注意只填1～9）
for(char value='1';value<='9';value++)
{
//进行剪枝判断是否有误
if(vailed_function(board,i,j,value)==false)
continue;//若不满足条件就跳掉
//做选择
board[i][j]=value;
if(backtrack(board,i,j+1))//回溯调用
{
return true;// 如果找到一个可行解，立即结束
}
//撤销选择
board[i][j]='.';//注意恢复为"."就是撤销选择
}
// 穷举完 1~9，依然没有找到可行解，此路不通
return false;
}
void solveSudoku(vector<vector<char>>& board) {
//输入为9*9的键盘，空白格用 '.' 表示。
// 需要在原地修改棋盘，将空白格子填上数字，得到一个可行解。
backtrack(board,0,0);
}
};
划分为k个相等的子集
下面方法可以解决，但是计算量较大，没有办法通过所有的测试案例，即使添加了排序也不行
class Solution {
public:
bool backtrack(vector<int>& nums,vector<int>& path, int index, int target)
{
// 递归终止条件
if(index==nums.size())//放完了
{
//path中每个数字都是target
for(int i=0;i<path.size();i++)
{
if(path[i]!=target)
return false;
}
return true;//通过全部检查那么就是true
}
//选择的列表，放入第几个桶
for(int i=0;i<path.size();i++)
{
//进行剪枝
if(path[i]+nums[index]>target)//已经满了
continue;
//才可以放
//做选择，放入第i个桶
path[i]+=nums[index];
if(backtrack(nums,path,index+1,target))//回溯开始处理下一个index+1
return true;//一找到马上返回true
//撤销选择
path[i]-=nums[index];
}
return false;//全部尝试完都不行，那就false
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
if(nums.size()<k)
return false;//根本没法分
//首先根据nums与k可以确定每个子集的和为多少
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%k!=0)//若整除不了k，那么就是不满足
return false;
int average=sum/k;//必然要整除，因为每个桶内都是整数
vector<int> path(k,0);//每个桶的数字之和
//由于只需要返回true与false，此处相当于没有result
int target=average;//每个桶数字的目标值。初始化为目标值，一直递减，等于0就是结果
// 添加排序的结果可以更快的触发回溯中的剪枝，进而加快
sort(nums.begin(),nums.end(),greater<int>());//从大到小排列（把大的数放前面）
return backtrack(nums,path,0,target);
}
};
换个思路去实现，也不行，当然可以加上index，让i从index开始，这样可以通过更多样例，但最终还是超时
class Solution {
public:
bool backtrack(vector<int>& nums, int k, int each_path, vector<bool>& used,int target)//index改为是球的索引
{
if(k==0)//全部桶都放满了
return true;
if(each_path==target)//当前桶放满了
{
each_path=0;//下个桶要置0
// 装满了当前桶，递归穷举下一个桶的选择
// 让下一个桶从 nums[0] 开始选数字
return backtrack(nums,k-1,each_path,used,target);
}
for(int i=0;i<nums.size();i++)
{
//剪肢:若这个球被用过了，或者超过阈值
if(used[i]==true || each_path+nums[i]>target)//当前球不能放
continue;
//做选择
each_path+=nums[i];
used[i]=true;//标记这个球被用过了
if( backtrack(nums,k,each_path,used,target))
{
return true;//若此次是结果就马上返回
}
//撤销选择
each_path-=nums[i];
used[i]=false;
}
return false;//一轮下来也没有结果，就是false
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
if(nums.size()<k)
return false;//根本没法分
//首先根据nums与k可以确定每个子集的和为多少
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%k!=0)//若整除不了k，那么就是不满足
return false;
int average=sum/k;//必然要整除，因为每个桶内都是整数
vector<bool> used(nums.size(),false);//用于确认这个球是否被使用过
int each_path=0;//每个桶的结果（由于在递归中会被判断，为此必须进行初始化！）
int target=average;//每个桶数字的目标值。
return backtrack(nums,k,each_path,used,target);
}
};
下面就是让i从index开始，这样可以通过更多样例，但最终还是超时
class Solution {
public:
bool backtrack(vector<int>& nums, int k, int each_path, vector<bool>& used, int index, int target)//index改为是球的索引
{
if(k==0)//全部桶都放满了
return true;
if(each_path==target)//当前桶放满了
{
each_path=0;//下个桶要置0
index=0;
// 装满了当前桶，递归穷举下一个桶的选择
// 让下一个桶从 nums[0] 开始选数字
return backtrack(nums,k-1,each_path,used,index,target);
}
for(int i=index;i<nums.size();i++)
{
//剪肢:若这个球被用过了，或者超过阈值
if(used[i]==true || each_path+nums[i]>target)//当前球不能放
continue;
//做选择
each_path+=nums[i];
used[i]=true;//标记这个球被用过了
if( backtrack(nums,k,each_path,used,i+1,target))
{
return true;//若此次是结果就马上返回
}
//撤销选择
each_path-=nums[i];
used[i]=false;
}
return false;//一轮下来也没有结果，就是false
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
if(nums.size()<k)
return false;//根本没法分
//首先根据nums与k可以确定每个子集的和为多少
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%k!=0)//若整除不了k，那么就是不满足
return false;
int average=sum/k;//必然要整除，因为每个桶内都是整数
vector<bool> used(nums.size(),false);//用于确认这个球是否被使用过
int each_path=0;//每个桶的结果（由于在递归中会被判断，为此必须进行初始化！）
int target=average;//每个桶数字的目标值。
return backtrack(nums,k,each_path,used,0,target);
}
};
下面是最终的解决方法，参考别人的代码，找到了新的剪枝的策略！！！
class Solution {
public:
bool backtrack(vector<int>& nums,vector<int>& path, int index, int target)
{
// 递归终止条件
if(index==nums.size())//放完了
{
// 其实这个地方不需要判断，因为当 index == num.length 时，所有球已经按要求装入所有桶，所以肯定是一个满足要求的解
// //判断path中每个数字都是target
// for(int i=0;i<path.size();i++)
// {
// if(path[i]!=target)
// return false;
// }
return true;//通过全部检查那么就是true
}
//选择的列表，放入第几个桶
for(int i=0;i<path.size();i++)
{
//剪枝2: 如果当前桶和上一个桶内的元素和相等，则跳过
// 原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
if (i > 0 && path[i] == path[i - 1])
continue;//参考思路：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solutions/1/by-lfool-d9o7
//进行剪枝
if(path[i]+nums[index]>target)//已经满了
continue;
//才可以放
//做选择，放入第i个桶
path[i]+=nums[index];
if(backtrack(nums,path,index+1,target))//回溯开始处理下一个index+1
return true;//一找到马上返回true
//撤销选择
path[i]-=nums[index];
}
return false;//全部尝试完都不行，那就false
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
if(nums.size()<k)
return false;//根本没法分
//首先根据nums与k可以确定每个子集的和为多少
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%k!=0)//若整除不了k，那么就是不满足
return false;
int average=sum/k;//必然要整除，因为每个桶内都是整数
vector<int> path(k,0);//每个桶的数字之和
//由于只需要返回true与false，此处相当于没有result
int target=average;//每个桶数字的目标值。初始化为目标值，一直递减，等于0就是结果
// 添加排序的结果可以更快的触发回溯中的剪枝，进而加快
sort(nums.begin(),nums.end(),greater<int>());//从大到小排列（把大的数放前面）
return backtrack(nums,path,0,target);
}
};
这题其实跟下面牛客网的题目很像，只是牛客网的这道题要求3的倍数和5的倍数不能放一起。通过递归即可解决～
关键是分解问题的思路～
#include <iostream>
#include <vector>
using namespace std;
bool callback(int sum3, int sum5, vector<int> other, int index)
{
//递归终止的条件
if(index==other.size())
{
return sum3==sum5;//最终检查两个是否相等
}
//要么加到3上，要么加到5上
return callback(sum3+other[index],sum5,other,index+1) || callback(sum3,sum5+other[index],other,index+1) ;
}
int main() {
int N;
cin>>N;
//由于所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中。
// 因此可以将输入先分为三个组，
int sum3=0;
int sum5=0;
vector<int> other;//其他数先放other中
int temp;
while(N--)
{
cin>>temp;
if(temp%5==0)//5的倍数
sum5+=temp;
else if(temp%3==0)//3的倍数在另一个组中（不包括5的倍数）
sum3+=temp;
else
other.push_back(temp);
}
if(callback(sum3,sum5,other,0))
{
std::cout<<"true";
}
else {
std::cout<<"false";
}
}
电话号码的数字组合
hash table与回溯算法的结合。
时间复杂度：O(3m×4n )， 其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有3m×4n种，需要遍历每一种字母组合。
空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。
class Solution {
public:
map<char,int> num_group=
{
{'a',2}, {'b',2}, {'c',2},
{'d',3}, {'e',3}, {'f',3},
{'g',4}, {'h',4}, {'i',4},
{'j',5}, {'k',5}, {'l',5},
{'m',6}, {'n',6}, {'o',6},
{'p',7}, {'q',7}, {'r',7}, {'s',7},
{'t',8}, {'u',8}, {'v',8},
{'w',9}, {'x',9}, {'y',9}, {'z',9}
};
void backtrack(string digits,string path,vector<string> &result,int index)
{
//回溯终止条件
if(path.size()==digits.size())
{
result.push_back(path);
return;
}
for(auto it=num_group.begin();it!=num_group.end();it++)
{
if(it->second!=(digits[index]-'0'))//注意是字符串
continue;//进行剪枝
//做选择
path.push_back(it->first);//添加字符
index=index+1;
backtrack(digits,path,result,index);
//撤销选择
path.pop_back();//删掉添加的
index=index-1;
}
}
vector<string> letterCombinations(string digits) {
vector<string> result;//digits的尺寸与result的一样~
string path;
//回溯算法
if(digits.size()!=0)//为空的情况下，会输出“”，但结果要求是空的，因此要加上这个判断
backtrack(digits,path,result,0);
return result;
}
};
目标和
看到这道题的第一思路就是采用回溯算法，跟组合和有点类似。注意终止条件应该是index==nums.size()而不是index==nums.size()-1
class Solution {
public:
void backtrack(vector<int>& nums, int each_path, int& results, int target, int index)
{
//递归终止条件
if(index==nums.size())//超越了~
{
if(each_path==target)
results++;
return;
}
//做选择
each_path+=nums[index];
backtrack(nums,each_path,results,target,index+1);//下一个
//撤销选择
each_path-=nums[index];
//做选择
each_path-=nums[index];//减法
backtrack(nums,each_path,results,target,index+1);//下一个
//撤销选择
each_path+=nums[index];//加回来
}
int findTargetSumWays(vector<int>& nums, int target) {
int each_path=0;
int results=0;
backtrack(nums,each_path,results,target,0);
return results;
}
};
此题也可以用动态规划Link去求解,但是思路比较绕，还是回溯算法比较直观。
重新安排行程
注意出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。从而导致计算超时。因此需要剪枝策略检查是否前后两个的机票一模一样。其次，通过预先的排序也可以保证输出的结果字典序最小，而不是全部算完再排序～
class Solution {
public:
bool backtrack(vector<vector<string>> tickets,vector<string> each_path,vector<string>& results, vector<bool> used)
{
//递归终止条件
if(each_path.size()==tickets.size()+1)//全部都用完了,应该为数目+1
{
results=each_path;
return true;
}
//选择列表(每次都重全部tickerts中选合适的)
for(int i=0;i<tickets.size();i++)
{
if(i>0
&& tickets[i][0]==tickets[i-1][0] && tickets[i][1] == tickets[i - 1][1]//完全一模一样的情况（那就没必要再测，跳过）
&& used[i-1]==false)
continue;// 如果跟上一个一样，且上一个没用过，那就跳过，因为只是重复使用
if(tickets[i][0]==each_path.back() //若当前的第一个跟数组中最后一个相等，那么就可以使用飞
&& used[i]==false //且当前机票没有被使用
)
{
//做选择
each_path.push_back(tickets[i][1]);//放入
used[i]=true;//标记当前机票已经被使用了
//回溯
if(backtrack(tickets,each_path,results,used))
return true;//找到了马上返回
//撤销选择
each_path.pop_back();
used[i]=false;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
//注意题目要求：所有的机票 必须都用一次 且 只能用一次。
// 有点类似排列（无重不可复选）
sort(tickets.begin(), tickets.end());//进行排序，(保证了,第一个找到的就是字典序最小的，同时也用于剪枝)
vector<string> results;
vector<string> each_path;
each_path.push_back("JFK");//把起点push进去
vector<bool> used(tickets.size(), false);//记录是否被用过
backtrack(tickets,each_path,results,used);
return results;
}
};
回溯算法解二叉树类题目
毕竟回溯算法也是递归的一种，而递归算法在二叉树类题目中非常常见，因此回溯算法也常用于解决二叉树类题目。 详细请见博客Link
总结：回溯算法与递归算法的区别
回溯算法模板的核心是在递归前做选择，递归后撤销选择。两者是很像的。 个人觉得回溯可以看出是递归的一种。
而对于二叉树中的递归（DFS） 回溯算法的关注点在「树枝」，DFS 算法的关注点在「节点」。如下代码所示。 直观理解就是回溯的前序和后序操作在for循环内，而DFS的前序和后序操作在for循环外。
// 回溯算法框架模板
void backtrack(...) {
if (到达叶子节点) {
return;
}
for (int i = 0, i < n; i++) {
// 做选择
...
backtrack(...)
// 撤销选择
...
}
}
// DFS 算法框架模板
void dfs(...) {
if (到达叶子节点) {
return;
}
// 做选择
...
for (int i = 0, i < n; i++) {
dfs(...)
}
// 撤销选择
...
}
回溯与二叉树的递归
回溯算法和 二叉树的递归（DFS） 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」。 通过下题来理解这个观点：
给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。 对于此题，如果直接用二叉树的递归遍历，代码如下：
void preOrder(TreeNode *root) {
if (root == nullptr) {
return;
}
//在前序的位置上
if (root->val == 7) {
// 记录解
res.push_back(root);//记录的为节点列表
}
preOrder(root->left);
preOrder(root->right);
}
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径：
void preOrder(TreeNode *root)
{
//到达就返回
if (root == nullptr) {
return;
}
// 尝试
path.push_back(root);//在每次“尝试”中，通过将当前节点添加进 path 来记录路径;
//记录结果及回溯调用
if (root->val == 7) {
// 记录解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退
path.pop_back();//在“回退”前，将该节点从 path 中弹出，以恢复本次尝试之前的状态。
}
进一步地，回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的 节点。
void preOrder(TreeNode *root)
{
// 剪枝（若值为3，就不会放入了）
if (root == nullptr || root->val == 3)
{
return;
}
// 尝试
path.push_back(root);
//不为7的时候虽然不记录结果，但是放到了path中了！！！
if (root->val == 7) {
// 记录解
res.push_back(path);
}
preOrder(root->left);
preOrder(root->right);
// 回退 path.pop_back();
}