---

前言

例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。

---

第9章：回溯法

回溯算法理论基础

什么是回溯算法

回溯是递归的“副产品”，只要有递归的过程就会有对应的回溯的过程

回溯法的性能

回溯法可以解决的问题

（1）组合问题：按照一定规则在N个数中找出k个数的集合
（2）切割问题：一个字符串按照一定规则切割，切割的方式
（3）子集问题：一个N个数的集合中有多少符合条件的子集
（4）排列问题：N个数按一定规则全排列，排列方式
（5）棋盘问题：N皇后、数独等问题

理解回溯法

回溯法解决的问题可以抽象为树形结构
回溯法解决的问题都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成了树的深度
（个人理解，其实就是正着遍历一步一步走，走到头，然后就往回撤，每撤一步，看看此时是否还能继续向前走（有分叉），如果能，就接着往前走，走到头，就往回撤）。写此类题代码时，就看看能不能正着走完，在走完处加上递归，回溯即可。

回溯法模板

三部曲
（1）确定回溯函数的返回值和参数
回溯算法中函数的返回值一般为void
（2）确定回溯函数的终止条件

（3）确定回溯搜素的遍历过程
for循环可以理解为横向遍历，递归过程则是纵向遍历，这样就把这棵树全遍历了

回溯算法的模板如下：

void backtracking(参数)
{if(终止条件){存放结果；return;}for(选择:本层集合中的元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking(路径,选择列表); //递归回溯,撤销处理结果}
}

组合问题

题目描述：
给出数值为1到n的n个数，返回 k个数的组合。（力扣 77）

回溯算法

通过递归来实现层叠嵌套，每一次递归过程中嵌套一个for循环，递归就可以解决多层嵌套循环的问题。
用树形结构来理解回溯

（1）确定递归函数的返回值和参数

vector<vector<int>> result; //存放符合条件的结果的集合
vector<int> path; //用来存放符合条件的单一结果
//startIndex用来记录递归的过程，集合从哪里开始遍历
void backtracking(int n,int k,int startIndex)

（2）确定回溯函数的终止条件
到达所谓的叶子节点

if(path.size()==k)
{result.push_back(path);return ;
}

（3）确定单层搜索的过程

//横向遍历
for(int i=startIndex;i<=n;i++)
{path.push_back(i);backtracking(n,k,i+1);path.pop_back();//回溯，撤销处理节点
}

如果n为100、k为50

完整代码如下：

class Solution
{private:vector<int> path;vector<vector<int>> result;void backtracking(int n,int k,int startIndex){if(path.size()==k){result.push_back(path);return ;}//树的横向遍历，一层一层的for(int i=startIndex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);push.pop_back();}}public:vector<vector<int>> combine(int n,int k){result.clear();path.clear();backtracking(n,k,1);return result;}
};

剪枝优化

n-(k-path.size())+1的由来：
path.size() ： 已经找的个数
k-path.size() ：还需找的个数
【x, n】（从x到n的左闭又闭区间）的数组长度起码应该是k-path.size()才有继续搜索的可能， 那么就有 n-x+1 = k-path.size() ， 解方程得 x = n+1 - (k-path.size()), 而且这个x是可以作为起点往下搜的 也就是for(i = s; i<=x; i++) 这里的x是可以取到的

完整代码如下：

class Solution
{private:vector<vector<int>>  result;vector<int>  path;void backtracking(int n,int k,int startIndex){if(path.size()==k){result.push_back(path);return ;}//优化的地方//k-path.size()代表还需要选取的元素个数//k-path.size()还需要搜素的个数for(int i=startIndex;i<=n-(k-path.size())+1;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();	}}public:vector<vector<int>> combine(int n,int k){backtracking(n,k,1);return result;}
};

组合总和(一)

题目描述 ：
在[1,2,3,4,5,6,7,8,9]这个 集合中找到和为n的k个数的组合，并且每种组合中不存在重复的数字。（力扣216）

回溯算法

三部曲：
（1）确定递归函数的返回值和参数

vector<vector<int>> result;
vector<int>  path;
/*targetSum 代表目标和k为题目中要求的k个数的集合sum为已经 收集的元素的总和，也就是path中元素的总和startIndex为下一层for循环搜索的起始位置*/
void backtracking(int targetSum,int k,int sum,int startIndex)

（2）确定终止条件

//k其实就是代表遍历的树形结构的深度
if(path.size()==k)
{if(sum==targetSum)result.push_back(path);return;
}

（3）确定单层搜索过程
处理过程和回溯过程是一一对应的，处理过程有加法操作，回溯过程中就要有对应的减法操作

for(int i=startIndex;i<=9;i++)
{sum+=i;path.push_back(i);backtracking(targetSum,k,sum,i+1);sum-=i; //回溯path.pop_back();//回溯
}

完整代码如下：

class Solution
{private:vector<int> path;vector<vector<int>> result;void backtracking(int targetSum,int k,int sum,int startIndex){if(path.size()==k){if(sum==targetSum)result.push_back(path);return ;}for(int i=startIndex;i<=9;i++){sum+=i;path.push_back(i);backtracking(targetSum,k,sum,i+1);sum-=i;path.pop_back();}}public:vector<vector<int>> combinationSum3(int k,int n){result.clear();path.clear();backtracking(n,k,0,1);return result;}
};

剪枝优化

思路通上；
代码如下：

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(int targetSum,int k,int sum,int startIndex){//剪枝优化if(sum>targetSum)return ;if(path.size()==k){if(sum==targetSum)result.push_back(path);return ;}//剪枝for(int i=startIndex;i<=9-(k-path.size())+1;i++){sum+=i;path.push_back(i);backtracking(targetSum,k,sum,i+1);sum-=i;path.pop_back();}			}public:vector<vector<int>> combinationSum3(int k,int n){result.clear();path.clear();backtracking(n,k,0,1);return result;}
};

电话号码的字母组合

题目描述：
给出一个仅包含数字2~9的字符串，返回所有它能表示的字母组合
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

回溯算法

（1）确定递归函数的参数

vector<string> result;
string s;//收集叶子节点的结果
//index用于记录遍历第几个数字；用来遍历题目输入的字符串，同时index也表示树的深度
void backtracking(const string &digits,int index)

（2）确定终止条件
终止条件就是index等于输入的数字个数即digits.size()

if(index==digits.size()){result.push_back(s);return ;
}

（3）确定单层遍历逻辑
获取下标index指向的数字，并找到对应的字符集（手机键盘的字符集）。使用for循环处理字符集

int digit=digits[index]-'0'; //将 index指向的数字转为int类型
string letters=letterMap[digit]; //获取数字对应的字符集
for(int i=0;i<letters.size();i++){s.push_back(letters[i]);

完整代码如下：

class Solution {private:const string letterMap[10]={"",//0"",//1"abc",//2"def",//3"ghi",//4"jkl",//5"mno",//6"pqrs",//7"tuv",//8"wxyz"//9};public:vector<string> result;string s;void backtracking(const string& digits,int index){if(index==digits.size()){result.push_back(s);return ;}int digit=digits[index]-'0';//将index指向的数字转为int类型string letters=letterMap[digit]; //获取数字对应的字符集for(int i=0;i<letters.size();i++){s.push_back(letters[i]);backtracking(digits,index+1);s.pop_back();}}vector<string>  letterCombinations(string digits){s.clear();result.clear();if(digits.size()==0){return result;}backtracking(digits,0);return result;}
};

组合总和（二）

题目描述：
给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合（力扣39）
candidates中的数字可以无限制地被重复选取

回溯算法

三部曲：
（1）确定递归函数的参数
对于组合问题，什么时候需要startIndex呢？
如果是在一个集合中求元素组合，那么就需要startIndex。如果是在多个集合中求元素组合，各个集合之间相互不影响，那么就不需要startIndex

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &candidates,int target,int sum,int startIndex)

（2）确定终止条件
终止条件，sum大于target和sum等于target。当sum等于target时需要 收集结果

if(sum>target){return ;
}
if(sum==target) {result.push_back(path);return ;
}

（3）确定单层的搜索逻辑
可重复选取元素

for(int i=startIndex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);//关键点：不需要i+1，表示可以重复读取当前的数backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();
}

完整代码如下：

class Solution {private:vector<int> path;vector<vector<int>> result;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]);//不需要i+1，表示可以重复读取当前的数backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int> &candidates,int target){result.clear();path.clear();backtracking(candidates,target,0,0);return  result;}
};

剪枝优化

剪枝减的是那一部分呢
对于sum大于target的情况，代码依然会递归到下一层，再下一次结束递归。
这次剪枝优化，就是让递归在这次结束，减少一次递归算法

代码如下：

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 ;}//如果sum+candidates[i]>target就终止遍历for(int i=startIndex;i<candidates.size() && sum+candidates[i] <=target; i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int> &candidates,int target){result.clear();path.clear();sort(candidates.begin(),candidates.end());//需要排序backtracking(candidates,target,0,0);return result;}
};

组合总和（三）

题目描述：
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字在每个组合中只能使用一次。（力扣40）

分割回文串

题目描述：
给定一个字符串s，将s分割成一些子串，使每个子串都是回文字符串。（力扣131）

思路：
两个关键问题：
（1）切割问题
（2）判断回文

回溯算法

三部曲：
（1）确定递归函数的参数

vector<vector<string>> result;
vecctor<string> path;  //存放已经回文的子串
void backtracking(const string &s,int startIndex)

（2）确定递归函数的终止条件

void backtracking(const string &s,int startIndex)
{//如果起始位置大于s，则说明找到了一组分割方案if(startIndex >= s.size()){result.push_back(path);return ;}
}

（3）确定单层递归逻辑

for(int i=startIndex;i<s.size();i++)	{//是回文子串if(isPalindrome(s,startIndex,i)){//获取[startIndex,i]在s中的子串string str=}

判断一个 字符串是不是回文字符，可以使用双指针法，一个指针从前向后遍历，另一个指针从后向前遍历，如果前后指针所指向的元素是相等的，那么该字符串就是回文字符串
判断回文字符的代码如下：

bool isPalindrome(const string &s,int start,int end)
{for(int i=start,j=end;i<j;i++,j--){if(s[i]!=s[j]){return false;}}return true;
}

完整代码：

class Solution {private:vector<vector<string>> result;vector<string>  path;void backtracking(const string &s,int startIndex){//如果起始位置大于s，则说明已经找到了一组分割方案if(startIndex>=s.size()){result.push_back(path);return ;}for(int i=startIndex;i<s.size();i++){//判断是否是回文子串if(isPalindrome(s,startIndex,i)){//获取[startIndex,i]在s中的子串string str=s.substr(startIndex,i-startIndex+1);path.push_back(str);}else{//不是回文子串，跳过continue;}backtracking(s,i+1); //寻找i+1为起始位置的子串path.pop_back();}}bool isPalindrome(const string &s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s[i]!=s[j])return false;}return true;}public:vector<vector<string>> partition(string s){result.clear();path.clear();backtracking(s,0);return result;}
};

复原IP地址

题目描述：
给定一个只包含数字的字符串，复原它并返回所有可能的IP地址格式。（力扣93）

回溯算法

三部曲：
（1）确定递归函数的参数
startIndex用于记录下一层递归 分割的起始位置
pointNum用于记录添加“.”的数量

vector<string> result;//记录结果
//startIndex搜索的起始位置；ponitNum添加“.”的数量
void backtracking(string &s,int startIndex,int ponintNum)

（2）确定递归条件

if(pointNum==3)
{//.的数量为3时，分隔结束//判断第4段字符串是否合法，如果合法就放进result中if(isValid(s,startIndex,s.size()-10.+))
}

完整代码如下 ：

class Solution {private:vector<string> result; //记录结果//判断字符串s在左闭右闭区间[start,end]所组成的数字是否合法bool isValid(const string &s,int start,int end){if(start > end)return false;//0开头的数字不合法if(s[start]=='0' && start!=end)return false;int num=0;for(int i=start;i<=end;i++){//遇到非数字字符不合法if(s[i] > '9' || s[i] < '0')return false;//如果大于255则不合法num=num*10+(s[i]-'0');if(num>255)return false；}return true;}//startIndex:搜索的起始位置；pointNum：添加逗点的数量void backtracking(string &s,int startIndex,int pointNum){if(pointNum==3){//"."的数量为3时，分隔结束//判断第四段字符串是否合法，如果合法就放进result中if(isValid(s,startIndex,s.size()-1)){result.push_back(s);}return ;}for(int i=startIndex;i<s.size();i++){//判断[startIndex,i]这个区间的字符串是否合法if(isValid(s,startIndex,i)){//在i的后面插入一个逗点s.insert(s.begin()+i+1,'.');pointNum++;//插入逗点之后下一个子字符串的起始位置是i+2backtracking(s,i+2,pointNum);pointNum--;s.erase(s.begin()+i+1);}else break;}}public:vector<string> restoreIpAddresses(string s){result.clear();if(s.size()>12)return result;return result;}
};

子集问题

题目描述：
给定一组不含重复元素的整数数组nums，返回该数组所有可能包含的子集（力扣78）

回溯算法

（1）确定递归函数的参数

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &nums,int startIndex)

（2）确定递归的终止条件
当startIndex大于数组的长度时，遍历就终止了，没有元素可取了

if(startIndex >=nums.size())
{return ;
}

（3）确定单层搜索逻辑
求子集的过程就是遍历整棵树

for(int i=startIndex;i<nums.size();i++)
{path.push_back(nums[i]); //子集收集元素backtracking(nums,i+1);  //不重复取元素path.pop_back();
}

整体代码如下：

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int> &nums,int startIndex){result.push_back(path); //收集子集，要放在终止条件上面，否则会漏掉元素if(startIndex >=nums.size()){return ;}for(int i=startIndex;i<nums.size();i++){path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}public:vector<vector<int>> subsets(vector<int> &nums){result.clear();path.clear();backtracking(nums,0);return result;}
};

子集问题（二）

题目描述：
给定一个可能包含重复元素的整数数组nums，返回该数组所有可能包含的子集。（力扣90）

思路：
集合有重复元素，需要对子集去重
树层去重和树枝去重，这里是树层去重

代码如下：

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int> &nums,int startIndex,vector<bool> &used){result.push_back(path);for(int i=startIndex;i<nums.size();i++){/*时刻记住，递归是纵向遍历，for循环是横向遍历*//*递归看的是同一树枝*//*循环看的是同一树层*///如果used[i-1]==true,则说明同一树枝使用过candidates[i-1]//如果used[i-1]==false，则说明同一树层使用过candidates[i-1]//我们要跳过同一树层使用过的元素if(i>0 && nums[i]==nums[i-1] && used[i-1]==false)continue;path.push_back(nums[i]);used[i]=true;backtracking(nums,i+1,used);used[i]=false;path.pop_back();}}public:vector<vector<int>> subsetsWithDup(vector<int> &nums){result.clear();path.clear();vector<bool> used(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return result;}
};

递增子序列

题目描述：
给定一个整型数组，找到该数组的所有递增的子序列，递增子序列的长度至少是2。

回溯算法

（1）确定递归参数的参数

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> &nums,int startIndex)

（2）确定终止条件

（3）确定单层

unordered_set<int> uset; //使用set对本层元素进行去重
for(int i=startIndex;i<nums.size();i++)
{if()
}

完整代码如下：

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(vecctor<int> &nums,int startIndex){if(path.size()>1){//只要path有值就会，放入到result中，因为看for循环里面的那个判断条件，可知path锁存的值都是符合条件的值result.push_back(path);}unordered_set<int> uset; //使用set对本层元素进行去重for(int i=startIndex;i<nums.size();i++){//uset.find(nums[i])!=uset.end()说明uset容器里已经有nums[i]的值了if(!path.empty() && nums[i]<path.back() || uset.find(nums[i])!=uset.end()){continue;}uset.insert(nums[i]);  path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();//注意uset作用是记录本层元素是否重复使用，新的一层都会重新定义uset，uset只负责本层的逻辑，所以没必要pop }}public:vector<vector<int>> findSubsequences(vector<int> &nums){result.clear();path.clear();backtracking(nums,0);return result;}
};

哈希优化

用数组做哈希来记录本层元素是否重复使用进行优化

代码如下：

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int> &nums,int startIndex){if(path.size()>1){result.push_back(path);}int used[201]={0}; //使用数组进行去重操作，数值范围是[-100,100]for(int i=startIndex;i<nums.size();i++){if(!path.empty() && nums[i]<path.back() || used[nums[i]+100]==1){continue;}used[nums[i]+100]=1;//记录这个元素在本层用过了path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();}}public:vector<vector<int>> findSubsequences(vector<int> &nums){result.clear();path.clear();backtracking(nums,0);return result;}
};

排列问题（一）

题目描述：
给定一个没有重复数字的序列，返回其所有可能的全排列。（力扣46）

回溯法

三部曲：
（1）确定递归函数的参数

vector<vector<int>> result;
vector<int> path;
//used用于标记已经用过的元素
void backtracking(vector<int> &nums,vector<bool> &used)

（2）确定递归的终止条件

//找到一组结果
if(path.size()==nums.size())
{result.push_back(path);return ; 
}

（3）确定单层递归逻辑

for(int i=0;i<nums.size();i++)
{//path中已有元素if(used[i]==true){continue;}used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;
}

完整代码如下：

class Solution
{public:vector<vector<int>> result;vector<int> path;void backtracking(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(used[i]==true){continue;}used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permute(vector<int> &nums){result.clear();path.clear();vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}	
};

排列问题（二）

题目描述：
给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列

回溯算法

class Solution
{private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int> &nums,vector<bool> &used){if(path.size()==nums.size()){result.push_back(path);return ;}for(int i=0; i<nums.size();i++){//nums[i]==nums[i-1]代表同一层不能重复使用一样的元素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]);backtracking(nums,used);path.pop_back();used[i]=false;}}}public:vector<vector<int>> permuteUnique(vector<int> &nums){result.clear();path.clear();sort(nums.begin(),nums.end());vector<bool> used(nums.size(),false);backtracking(nums,used);return result;}
};

N皇后问题

题目描述：
N皇后问题研究的是如何将n个皇后放置在n*n的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的N皇后问题的解决方案。（力扣51）

回溯法

（1）确定递归函数的参数

//使用row记录当前遍历到棋盘的第几层
vector<vector<string>> result;
void backtracking(int n,int row,vector<string> &chessboard)

（2）确定递归的 终止条件
当递归到棋盘底层（也就是叶子节点）的时候，就可以收集结果并返回

if(row==n)
{result.push_back(chessboard);return ;
}

（3）确定单层搜索的逻辑

for(int col=0;col<n;col++)
{if(isValid(row,col,chessboard,n)){chessboard[row][col]='Q';backtracking(n,row+1,chessboard);chessboard[row][col]='.';}
}

（4）验证棋牌是否合法
不能同行；不能同列；不能同斜线（45度角和135度角）

bool isValid(int row,int col,vector<string> &chessboard,int n)
{int count=0;//检查列for(int i=0;i<row;i++){if(chessboard[i][col]=='Q')return false;}//检查45度角直线上是否有皇后for(int i=row-1,j=col-1;i>=0  && j>=0;i--,j--){if(chessboard[i][j]=='Q')return false;}//检查135度角直线上是否有皇后for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){if(chessboard[i][j]=='Q')return false;}return true;
}

完整代码如下：

class Solution
{private:vector<vector<string>> result;//n为输入的棋盘大小//row表示当前递归到棋牌的第几行了void backtracking(int n,int row,vector<string> &chessboard){if(row==n){result.push_back(chessboard);return ;}for(int col=0;col<=n;col++){if(isValid(row,col,chessboard,n)){chessboard[row][col]='Q';backtracking(n,row+1,chessboard);//时刻谨记 for循环是横向遍历，每次递归完找完一个分支后，然后 回溯的时候都要重新开始，恢复到以前 的状态chessboard[row][col]='.';//回溯}}}bool isValid(int row,int  col,vector<string> &chessboard,int n){int count=0;//检查列for(int i=0;i<row;i++){if(chessboard[i][col]=='Q')return false;}//检查45度直线是否有皇后for(int i=row-1,j=col;i>=0 && j>=0;i--,j--){if(chessboard[i][j]=='Q')return false;}//检查135度角是否有皇后for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){if(chessboard[i][j]=='Q')return false;}return true;}public:vector<vector<string>> solveNQueens(int n){result.clear();vector<vector<string>> chessboard(n,string(n,'.'));backtracking(n,0,chessboard);return result;}
};