本章回溯算法可以解决的问题如下：
回溯法的模板：
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
77. 组合
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
思路分析
回溯法三部曲
- 递归函数的返回值以及参数
这里直接使用全局变量来操作,一个存放最终的结果集,一个存放符合条件的临时集合.这样我们也就不需要返回值了.
参数:数据个数n,组合个数k 每次需要传入.另外也需要传入下次循环的起始位置,方便下一次其他数据进行组合.
vector<int> path; vector<vector<int>> result; void backtracking(int n,int k,int startIndex){ ... }
- 回溯函数终止条件
当path.size() == k了,则说明我们已经找到了大小为k的组合了. 结束递归
if(path.size()==k){ result.push_back(path); return;//结束递归 }
- 单层搜索过程
回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i,递归回来之后进行回溯,继续循环.
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历 path.push_back(i); // 处理节点 backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始 path.pop_back(); // 回溯，撤销处理的节点 }
代码优化
可以剪枝的地方在递归中每一层的for循环条件处。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置。
所以中间for循环的条件可以改造为:i <= n-(k-path.size())+1
参考代码
vector<vector<int>> result; vector<int> path; void backtracking(int n,int k,int startIndex) { //回溯结束条件 if(path.size()==k) { result.push_back(path); return; } //剪枝优化1 // if(path.size()+n-startIndex+1 < k) { // return; // } // for(int i = startIndex;i<= n-(k-path.size())+1;i++){//剪枝优化2 for(int i = startIndex; i<= n; i++) { // path.push_back(i); backtracking(n,k,i+1);//递归+ path.pop_back();//回溯 } } vector<vector<int>> combine(int n, int k) { backtracking(n,k,1); return result; }
216.组合总和III
题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路分析
本题相对于上个题只是多个 之和为n的限制,其他的处理思路和上题类似
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> path; vector<vector<int>> result; void backtracking(int n,int k,int startIndex,int sum) { if(path.size()==k){ if(sum == n){ result.push_back(path); } return; } for(int i = startIndex;i <= 9 - (k-path.size())+1;i++){ path.push_back(i); backtracking(n,k,i+1,sum+i); path.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { backtracking(n,k,1,0); return result; }
17. 电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
思路分析
输入：“23”，抽象为树形结构，如图所示：
图中可以看出遍历的深度就是输入的 字符串的长度，而叶子节点就是我们要收集的结果，宽度为 字符所对应的字符串长度 ,如2==>abc
回溯三部曲
确定递归参数和返回值
参数:需要传入输入的字符串digits,当前递归到的digits的index
返回值:依旧定义两个个全局变量,一个是最终结果集,一个存放临时组合数.所以返回值为void 可以看出回溯类型的递归通常没有返回值
确定递归结束条件
如果index==digits.size(),则说明已经找到了满足的组合数,递归结束
确定单层递归逻辑
先从递归的index拿到对应的字符串,然后开始循环,递归,回溯…
参考代码
#include<bits/stdc++.h> using namespace std; //LeetCode17:https://leetcode.cn/problems/letter-combinations-of-a-phone-number //本题属于组合问题的 “多个集合的组合” string path; vector<string> result; string arr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; void backtracking(string& digits,int startIndex) { //结束条件 if(startIndex==digits.size()) { result.push_back(path); return; } int num = digits[startIndex] - '0';//要遍历的字符串数组下标 for(char ch : arr[num]) { //横向for循环 path.push_back(ch); backtracking(digits,startIndex+1);//纵向递归 path.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits=="") {//特殊情况判断 return result; } backtracking(digits,0); return result; }
39. 组合总和
题目描述
给你一个 无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []
参考代码
#include<iostream> using namespace std; //本题同LeetCode77只是结束条件变化了，其他思路都一致 vector<int> path; vector<vector<int>> result; void backtracking(vector<int>& candidates, int target,int startIndex,int sum){ if(sum > target){ return; }else if(sum == target){ result.push_back(path); return; } for(int i = startIndex; i < candidates.size(); i++){ path.push_back(candidates[i]); backtracking(candidates,target,i,sum+candidates[i]); path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates,target,0,0); return result; }
40. 组合总和 II
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
思路分析
本题要是仅凭读题感觉好像比上一题还简单,但是看过示例之后就会发现,是我太天真了!😱😱😱 主要有如下区别:
本题candidates中的每个数字在每个组合中只能使用一次
本题数组candidates的元素是有重复的,而 39 组合总和 是无重复的数组
本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。
很容易想到的思路:把所有组合求出来，再用set或者map去重，但这么做很容易超时！
组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。 (同一树枝:也就是组合中数的维度,组合中的数可以有重复的. 同一树层:数组中数循环的维度,由于数组有重复数,所以上次可以循环到这个数,下次循环也可以到这个数,但是这俩数是在同一for循环内的.)
那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
去重之前,我们需要对数进行排序.(为什么排序,大家可以思考一下)
树形结构如图所示
used数组存储的是本层数的使用情况, 用于判断是否是同一个树层
算法设计
⭐️⭐️⭐️回溯三部曲
确定递归函数参数和返回值
每次需要传入数组candidates,循环的下一个位置下标 startIndex,当前组合数的和 sum,目标值 targetSum,以及用于去树层重的used数组
由于我们使用全局变量来保存结果值,所以并不需要定义返回值.
确定递归终止条件
当sum>=targetSum时,结束递归. 当 = 时,还要将其加入到结果集中(由于后序会有剪枝操作,所以sum>targetSum可以省略)
确定单层递归逻辑
先判断当前数和上一个是否是同一个树层,如果是则跳过该数,循环下一个数. 否则更新sum,path数组,继续递归,递归完毕之后进行回溯,再继续判断循环下一个数.
⭐️⭐️⭐️本题核心就是去重: candidates[i] == candidates[i - 1]
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过,不必去重
used[i - 1] == false，说明同一树层candidates[i - 1]使用过,需要去重
🌟🌟🌟代码剪枝:本题剪枝方案和上题类似
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> path; vector<vector<int>> result; void backtracking(vector<int>& candidates, int target,int startIndex,int sum,vector<bool>& used) { if(sum > target) { return; } else if(sum == target) { result.push_back(path); return; } for(int i = startIndex; i < candidates.size(); i++) { if(i >=1 && candidates[i]==candidates[i-1] && used[i-1]==false) { //数层去重 continue; } used[i] = true; path.push_back(candidates[i]); backtracking(candidates,target,i+1,sum+candidates[i]); path.pop_back(); used[i] = false; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<bool> used(candidates.size(),false); sort(candidates.begin(),candidates.end()) ;//排序 backtracking(candidates,target,0,0,used); return result; }
