回溯

组合问题

Leecode 77. 组合

链接：https://leetcode.cn/problems/combinations/

刚开始接触回溯很多地方都想不清楚，先剖析一下完整代码

vector> result; // 存放符合条件结果的集合
vector 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(); // 回溯，撤销处理的节点}// 执行过程要依赖下一层的for函数// 比如当path刚刚push进1的时候，会继续递归进入第二层，利用第二层的for循环push进2，然后继续递归到第三层，利用第三层的for循环push进3···到了第四层后会push进去4，之后再次递归——因为此时startIndex是5，所以不会再进入for循环// 具体pop的细节：当进入第三层的时候会首先判断当前path的大小，已经等于2了，那么就会return，return到第二层（此时startIndex等于2），pop出去后会进入第二层的for循环，然后会在第二层把3加进去，然后进入第四层// 情形相似，第四层也会return，结果还是在第二层中利用for循环把4给push进去了，然后递归第五层，因为n就是4，所以到了第五层pop后return到第二层没法for循环，return到第一层的pop，然后把元素1给pop出来// 此时result数组记录了"12","13","14"// 然后第一层的for循环中i = 2，相当于从原来的第一层变成了现在的第二层，然后接着递归···
}

下面是AC代码

class Solution {
public:vector> res;vector path;void recursion(int n,int k,int start){if(path.size() == k){res.push_back(path); return; }for(int i=start;i<=n;i++){path.push_back(i);recursion(n,k,i+1); // 递归只是幌子，首元素相同的path全是在第二层递归完成的path.pop_back();}}vector> combine(int n, int k) {// 首先搞清楚return的逻辑// 就是当前数组中已经记录了k个值，我们就returnrecursion(n,k,1);return res;}
};

剪枝操作：因为代码中有很多无效的循环，因此我们可以添加剪枝操作让程序运行的更快

那么我们思考如何进行剪枝：假设n = 4并且k = 4，当此时vector中已经存储了一个元素，那么我们可以从3，可以从4开始遍历么？显然是不行的，因为n最大就是4，若从3或者4开始填充数组，那么元素显然是不够用的，最多可以从2开始——基于此段描述，我们可以对递归前的for循环的范围进行限制（当前元素越少，选择就越少）：(k - path.size())是我们还需要多少元素，n是我们一共有多少元素，n - (k - path.size())是我们循环开始时元素的选择空间有多大，比如说我们已经有了元素1，还差3个元素，n是4，那么接下来循环可以从1开始，也可以从2开始，所以n - (k - path.size()) + 1得到的就是合法的最大上界

class Solution {
public:vector> res;vector path;void recursion(int n,int k,int start){if(path.size() == k){res.push_back(path); return; }for(int i=start;i<=n - (k - path.size()) + 1;i++) // 此处剪枝{path.push_back(i);recursion(n,k,i+1);path.pop_back();}}vector> combine(int n, int k) {recursion(n,k,1);return res;}
};

Leecode 216. 组合总和 III

链接：https://leetcode.cn/problems/combination-sum-iii/

这次回溯要求元素的和是固定的，所以我们在递归的时候需要维护当前数组中的元素和

class Solution {
public: vector> res;vector vec;void recursion(int k,int n,int sum,int step){// 还可以再剪，当sum > n，直接reuturnif(sum > n) return;if(vec.size() == k){if(sum == n) res.push_back(vec);return;}for(int i=step;i<=min((n - sum),9);i++) // 剪枝{vec.push_back(i);recursion(k,n,sum + i,i+1);vec.pop_back();}}vector> combinationSum3(int k, int n) {recursion(k,n,0,1);return res;}
};

Leecode 17. 电话号码的字母组合

链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

首先我们需要用一个string数组（其实也能当做是二维数组）记录数字和其映射的英文字母

显然这个题目也是要记录当前步数的，我们重新写一个回溯函数，然后在题目给的letterCombinations中调用这个回溯函数

至于传入letterCombinations的digits，我们之后在recursion中处理：

进入recursion函数中首先还是判断递归的结束条件，就是步数 == digits.size()时，我们记录结果并且return

然后就是字符串的处理，也是一般递归函数没有的操作

因为我们是一个字符一个字符进行处理，所以我们要取传入的digits中的一个字符进行操作，怎么取？就是定义的步长

取出来当前字符对应的char后将其转化为数字num，然后用num作为索引读取当前num对应的字符串tar

后面就是喜闻乐见的for循环，i的返回肯定是0到tar.size()

还有一点需要注意的是在for循环中递归的参数是step + 1而不是i + 1，因为再次递归我们就要处理第二个字符对应的字符串了

// 居然s都能pushback这也太秀了吧
class Solution {
public:string s;vector res;const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};void recursion(string str,int step){if(s.size() == str.size()){res.push_back(s);return;}// 然后我们把当前step指向的字符转化成数字int num = str[step] - '0';// 取当前数字对应的字符串string tar = letterMap[num];for(int i=0;is.push_back(tar[i]);recursion(str,step + 1); // 注意这里一定是step + 1s.pop_back();}}vector letterCombinations(string digits) {s.clear();res.clear();if(digits == "") return res;recursion(digits,0); // 外侧直接把字符串给送进去return  res;}
};

Leecode 39. 组合总和

其实和我们之前做的77题不太一样，因为这里的元素是可以重合的，如果按照下面这样写，我们得到的是总和为target的排列而不是组合

class Solution {
public:vector> res;vector vec;void recursion(vector& candidates,int sum,int target){if(sum > target) return;if(sum == target){res.push_back(vec);return;}for(int i=0;ivec.push_back(candidates[i]);recursion(candidates,sum + candidates[i],target);vec.pop_back();}}vector> combinationSum(vector& candidates, int target) {recursion(candidates,0,target);return res;}
};
//candidates = [2,3,6,7]
//target = 7
//output: [[2,2,3],[2,3,2],[3,2,2],[7]]

如上，显然是不合法的

那么我们只要保证元素是递增的不就好了

我们还可以加入剪枝操作，就是保证当前数组中的元素是递增的，那么若当前值加上sum已经大于target了，后面的值也就不用看了

class Solution {
public:vector> res;vector vec;void recursion(vector& candidates,int sum,int target){if(sum > target) return;if(sum == target){res.push_back(vec);return;}for(int i=0;i//保证元素是递增的就完事儿了if((!vec.empty() && candidates[i] >= vec[vec.size()-1])||vec.empty()) vec.push_back(candidates[i]);else continue;recursion(candidates,sum + candidates[i],target);vec.pop_back();}}vector> combinationSum(vector& candidates, int target) {sort(candidates.begin(),candidates.end()); // 先排序，保证数组中的元素是递增的，这样当前sum + candidates[i] > target，也就不需要往后遍历了recursion(candidates,0,target);return res;}
};

如此就，快乐AC

但是还有一种做法是保留step，并且每次递归时step就保持原值

class Solution {
private:vector> result;vector path;void backtracking(vector& 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() && sum + candidates[i] <= target; i++) { // 此处还可以加入剪枝操作sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数sum -= candidates[i];path.pop_back();}}
public:vector> combinationSum(vector& candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0);return result;}
};

有点深度奥！