文章目录

• • 一、引言
  • 二、回溯法基本逻辑
  • 三、回溯法代码模板
  • 三、回溯法常见问题
  • • 3.1 组合
    • • 逻辑
      • 代码
    • 3.2 子集
    • • 逻辑
      • 代码
    • 3.3 子集Ⅱ（未解答）
    • • 逻辑
      • 代码
    • 3.4 分割回文串
    • • 逻辑
      • 代码
    • 3.5 组合总和Ⅰ
    • • 逻辑
      • 代码
    • 3.6 组合总和Ⅱ（未解答）
    • • 逻辑
      • 代码
    • 3.7 组合总和Ⅲ
    • • 逻辑
      • 代码
    • 3.8 全排列Ⅰ
    • • 逻辑
      • 代码
      • 优化
      • 代码
      • 优化
      • 代码
    • 3.9 全排列Ⅱ（未解答）
    • • 逻辑
      • 代码
    • 3.10 解数独（未解答）
    • • 逻辑
      • 代码
    • 3.11 N皇后Ⅰ（未解答）
    • • 逻辑
      • 代码
    • 3.12 N皇后Ⅱ（未解答）
    • • 逻辑
      • 代码

一、引言

许多情况下，回溯算法相当于暴力搜索的方式 进行实现，性能一般不理想。但是对于某些问题，就算采用最复杂的时间复杂度能求得结果，也是一种里程碑式的进步。

回溯算法一个实际的具体例子就是在一套新房子内摆放家具的问题。
开始什么也不拜访，之后是每件家具被摆放到室内的某个部分，如果所有家具都摆好且都满意，则算法结束。
如果摆放了某一个家具之后，但是对于当前拜访的方式不理想，那么我们必须撤销这一步，尝试其他的摆放方式。如果我们一直撤销，直到撤销到第一个摆放的家具，那么不存在满意的家具摆放的方法；否则我们将在满意的摆放位置上结束算法。
在摆放过程中，直接不去考虑某些必然不满意的摆放方法，例如将沙发摆进厨房必然是不满意的摆放方法。这种直接不考虑不合理子集的方式就叫做 剪枝。

二、回溯法基本逻辑

回溯的原理就是采用递归的方式 ，将问题看作为解空间树的形式。注意是看作空间树的形式，具体的数据结构可能是列表、树、字符串等等
在解空间树中，按照深度优先的方式，从根结点出发进行搜索，搜索至任意结点时，先判断该结点是否包含问题的解①如果不包含，则向祖先节点回溯（即退出该层递归）②如果包含，则进入该子树，继续进行深度优先。

三、回溯法代码模板

// t表示当前递归深度
// n为树高，用来控制递归深度
// f(n,t)表示在当前扩展结点处未搜索过的子树的起始编号
// g(n,t)表示在当前扩展结点处未搜索过的子树的终止编号
// h(i)表示在当前扩展结点处x[t]的第i个可选值
// Constraint(t)表示在当前扩展节点处的约束函数
// Bound(t)表示在当前扩展节点处的界限函数
void backtracking(int t){if(t>n){//表示搜索到了叶节点outPut(x);//输出可行解x}else{// for(int i = f(n,t) ; i <= g(n,t) ; i++){x[t] = h(i); // 收集结果if(Constraint(t)&&Bound(t)){// 通过约束和界限进行剪枝操作，满足时才继续向下递归backtracking(t+1);}}}
}

三、回溯法常见问题

3.1 组合

力扣题库序号77

逻辑

以n = 4， k=2为例

代码

class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;// n: 数字1~n进行组合	k:组合列表的大小    vector> combine(int n, int k) {backtracking(n,k,1);return rst;}// 从[startIndex,n]中找到大小为k的排列// 例如：backtracking(n,k,1)   n: 数字1~n进行组合	k:组合列表的大小   1表示从第1个数开始void backtracking(int n,int k,int startIndex){// 如果当前路径大小等于组合列表的大小，表示收集到了叶节点，那么push入最后的结果if(path.size()==k){rst.push_back(path);return;}// 从startIndex~nfor(int i=startIndex;i// 每一层将i放入path.push_back(i);// 继续从递归（从[i+1,n]中找到剩余大小的排列）backtracking(n,k,i+1);// 退出该层时将i移出，就是回溯的过程path.pop_back();}return ;}
};

可以输出path，查看path收集数据的变化。

3.2 子集

力扣题库序号78

逻辑

组合和子集区别就是，子集不限制大小，而组合规定了大小。
表现在实现的代码中就是，子集需要在递归出口时收集结果，而组合需要在数据变换后就收集结果。

在代码实现时需要注意，本题的集合是已经给出的非连续的数字列表；而上一题的组合题是给出一个数字范围。

代码

class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> subsets(vector& nums) {rst.push_back({});backtracking(nums,0);return rst;}void backtracking(vector &nums,int startIndex){for(int i = startIndex;ipath.push_back(nums[i]);// 在每一次数据变化时进行结果的收集。rst.push_back(path);// 继续从递归（i+1之后的组合）backtracking(nums,i+1);// 退出该层时将nums[i]移出，就是回溯的过程path.pop_back();}return;}
};

3.3 子集Ⅱ（未解答）

力扣题库序号90

逻辑

代码

class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> subsetsWithDup(vector& nums) {rst.push_back({});sort(nums.begin(),nums.end());backtracking(nums,0);return rst;}void backtracking(vector &nums,int startIndex){for(int i = startIndex;iif(i==startIndex||nums[i]!=nums[i-1]){path.push_back(nums[i]);// 在每一次数据变化时进行结果的收集。rst.push_back(path);// 继续从递归（i+1之后的组合）backtracking(nums,i+1);// 退出该层时将nums[i]移出，就是回溯的过程path.pop_back();}}return;}
};

3.4 分割回文串

力扣题库序号131

逻辑

这类题通常需要分析切割的逻辑
切割范围就是每一次的startIndex~i的范围，注意startIndex≠i，因为i是在不断变化的
剪枝的操作就是本次切割的范围产生的字符串并不是回文子串，那么本次切割不再考虑，直接考虑i+1后startIndex~i切割的字符串。
例如aabb，

第一次切割0 ~ 1 =>“a”	第二次切割1 ~ 2 => “a”	第三次切割2 ~ 3 => “b”	第四次切割3 ~ 4 => “b”	产生【“a”，“a”，“b”，“b”】
-	第二次切割1 ~ 3 => “ab” “ab”不是回文，之后不管怎么切都不可能符合要求，因此之后的分支就不再考虑，这就是剪枝操作
-	第二次切割1 ~ 4 => “abb” "abb"不是回文，之后不管怎么切都不可能符合要求，剪枝。
第一次切割0 ~ 2 => “aa”	第二次切割2 ~ 3 => “b”	第三次切割3 ~ 4 => “b”		产生【“aa”，“b”，“b”】
第一次切割0 ~ 3 => “aab” "aab"不是回文，之后不管怎么切都不可能符合要求，剪枝
第一次切割0-4 => “aabb”				产生【“aabb”】

手绘以aab为例

代码

class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> partition(string s) {backtracking(s,0);return rst;}void backtracking(string s, int startIndex){// 递归出口：割到最后一位，收集结果if(startIndex>=s.size()){rst.push_back(path);}for(int i=startIndex;istring a;// a = s[startIndex~i]for(int k=startIndex;ka += s[k];}// 剪枝操作，如果是回文串才加入并且向后切割，否则不再向下递归if(isCycle(a)){// 将已经切的回文字符串加入结果，并且递归切割从i之后开始的字符串path.push_back(a);backtracking(s,i+1);// 退出该层时将a移出，就是回溯的过程path.pop_back();}}}// 判断是否回文bool isCycle(string s){for(int i=0;iif(s[i]!=s[s.size()-i-1])return false;}return true;}
};

3.5 组合总和Ⅰ

力扣题库序号39

逻辑

代码

class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> combinationSum(vector& candidates, int target) {backtracking(candidates, target, 0);return rst;}// candidates 从 startIndex开始 寻找总和为 target 的组合void backtracking(vector& candidates, int target, int startIndex){// 如果要求总和为0，代表path内的数字已经满足总和if(target==0){rst.push_back(path);return;}else{for(int i=startIndex;i// 剪枝操作：当candidate[i] <= target时才满足，// 			否则代表本次组合必然不符合target, 因为没有candidate中的数均为正数if(target>=candidates[i]){path.push_back(candidates[i]);// 因为可以重复选取，因此还是从i开始；如果不能重复，则从i+1开始。backtracking(candidates,target-candidates[i],i);path.pop_back();  }}}}
};

3.6 组合总和Ⅱ（未解答）

力扣题库序号40

逻辑

去重

代码

class Solution {
public:vector> rst;vector path;vector> combinationSum2(vector& candidates, int target) {sort(candidates.begin(), candidates.end());backtracking(candidates,target,0);return rst;}void backtracking(vector& candidates, int target,  int startIndex){if(target==0){rst.push_back(path);return;}else{for(int i = startIndex;iif(i==startIndex||candidates[i]!=candidates[i-1]){path.push_back(candidates[i]);backtracking(candidates,target-candidates[i],i+1);path.pop_back();}}}}
};

3.7 组合总和Ⅲ

力扣题库序号216

逻辑

代码

class Solution {
public:vector> rst;vector path;vector> combinationSum3(int k, int n) {backtracking(k, n ,1);return rst;}void backtracking(int k, int n ,int startIndex){if(n==0&&k==0){rst.push_back(path);return;}if(n!=0&&k!=0){for(int i=startIndex;i<10;i++){if(n>=i){path.push_back(i);backtracking(k-1, n-i,i+1);path.pop_back();  }}}}
};

3.8 全排列Ⅰ

力扣题库序号46

逻辑

选择没有选取过的元素作为path数组，当path数组大小等于nums的大小的时候进行结果收集。
因此思路就是建立used数组标记是否使用过nums中的某个元素。

代码

// 通过used标记使用过的元素
class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> permute(vector& nums) {// 标记nums中使用过的元素vector used(nums.size(),false);backtracking(nums,used);return rst;}void backtracking(vector& nums, vector used){// 当path数组大小==nums数组大小的时候，表示元素已经被全部使用if(path.size()==nums.size()){rst.push_back(path);return ;}else{for(int i=0;i// 如果没有被使用，则加入path数组，并且对used进行标记if(used[i]==false){path.push_back(nums[i]);used[i] = true;// 向下递归backtracking(nums,used);// 回溯used[i] = false;path.pop_back();}}}}
};

优化

本题的思路就是如何判断某元素是否被使用，因此可以通过交换元素在nums中的位置来判断元素是否被使用
nums中靠前的元素被使用，靠后的元素没有被使用，被使用元素的个数就是path数组的大小。
因此backtracking调用时，startIndex使用当前path数组的大小。

代码

// 将使用过的元素放置
class Solution {
public:// 最终返回结果列表vector> rst;// 每一次结果vector path;vector> permute(vector& nums) {backtracking(nums,0);return rst;}void backtracking(vector& nums, int startIndex){if(startIndex==nums.size()){rst.push_back(path);return ;}else{for(int i=startIndex;i// 将使用过的nums[i]前置path.push_back(nums[i]);swap(nums[startIndex],nums[i]);backtracking(nums,path.size());// 回溯：移出元素并且恢复原来的元素位置关系swap(nums[startIndex],nums[i]);path.pop_back();}}}};

优化

继续优化，backtracking被调用时其startIndex均为调用函数的startIndex+1，
而最后只需要startIndex指向最后一位时，就可以进行元素收集，因为nums是进行交换产生的，那么直接收集当前nums的元素就可以。

代码

class Solution {
public:vector> rst;vector> permute(vector& nums) {backtracking(nums,0);return rst;}void backtracking(vector& nums, int startIndex){// 交换至最后一位进行结果的收集if(startIndex==nums.size()){rst.push_back(nums);return ;}else{for(int i=startIndex;iswap(nums[startIndex],nums[i]);backtracking(nums,startIndex+1);// 被调用的startIndex参数 = 调用函数的startIndex+1swap(nums[startIndex],nums[i]);}}}};

3.9 全排列Ⅱ（未解答）

力扣题库序号47

逻辑

代码

class Solution {
public:vector> rst;vector path;vector> permuteUnique(vector& nums) {sort(nums.begin(),nums.end());vector used(nums.size(),0);backtracking(nums,0,used);return rst;}void backtracking(vector& nums, int startIndex, vector used){if(startIndex == nums.size()){rst.emplace_back(path);return;}for(int i = 0; i < (int)nums.size(); i++){// if(used[i] == 1)continue;// if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){//     continue;// }if(i==0||nums[i-1]!=nums[i]||used[i-1]==1){if(used[i]==0){path.emplace_back(nums[i]);used[i] = 1;backtracking(nums,startIndex+1,used);path.pop_back();used[i] = 0;}}}}
};

3.10 解数独（未解答）

力扣题库序号37

逻辑

代码

3.11 N皇后Ⅰ（未解答）

力扣题库序号51

逻辑

代码

3.12 N皇后Ⅱ（未解答）

力扣题库序号52

逻辑

代码