数据结构与算法学习day21-回溯法

一、组合

1.题目

. - 力扣（LeetCode）

2思路

把组合问题抽象成树形结构（N叉树）

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现n相当于树的宽度，k相当于树的深度。

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

那么如何在这个树上遍历，然后收集到我们要的结果集呢？

图中每次搜索到了叶子节点，我们就找到了一个结果。

相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。

按照递归法写法去写回溯法即可。

1.递归函数的返回值以及参数

函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。

然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的集合从哪里开始遍历，防止取到重复值。

2.回溯函数终止条件

path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。

3.单层搜索的过程

for循环每次从startIndex开始遍历，然后用path保存取到的节点i。

可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。

总体代码：

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;}for (int i = startIndex; i <= n; 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.题目

17. 电话号码的字母组合 - 力扣（LeetCode）

2.思路

2.1 数字和字母如何映射

定义一个二维数组letterMap来映射。

同时需要把字符转换成数字

2.2 回溯法来解决n个for循环的问题

回溯三部曲：

1.传入参数

参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。

2.终止条件

当遍历到字符串最后一个字符时，把子集加入到结果中。

3.单层遍历逻辑

把字符转换为数字，同时映射出字符串。用for循环进行遍历目前字符串。需要注意的是，每次遍历字符串从0开始，因为这道题是多个字符串的组合题。上面那题属于单个数组的组合题。

总体代码：

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;//index为处理的位数void backtracking(const string& digits,int index){if(index == digits.size()){result.push_back(s);return;}//转换成数字int  digit = digits[index] - '0';string temp = letterMap[digit];for(int i = 0;i < temp.size();i++){s.push_back(temp[i]);backtracking(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0) return result;backtracking(digits,0);return result;}
};

 三、组合总和

1.题目

39. 组合总和 - 力扣（LeetCode）

2.思路

本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。为了不重复，只能往后取数字。

2.1 传入参数

除了原来给的两个参数candidate和target，另外加了sum和index。sum用来计算取的值总和大小，index用来标记for循环的开始位置。因为这道题属于单集和求组合。

2.2 终止条件

如果sum大于target，则回溯。

如果sum等于target，则加入result。

2.3 单层循环逻辑

sum加上当前值，并把当前值加入到path子集，进行下一步的元素寻找。大于或者等于则返回，进行回溯，同时sum要把当前值减掉。

总体代码： 

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target,int sum,int index){if(sum > target) return;if(sum == target){result.push_back(path);return;}for(int i = index; i < candidates.size();i++){sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);//递归path.pop_back();                      //回溯sum -= candidates[i];}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};