回溯组合篇--代码随想录算法训练营第二十一天| 回溯算法介绍，77. 组合，216.组合总和III，17.电话号码的字母组合，39. 组合总和，40.组合总和II
回溯算法介绍
https://www.programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80
终止条件：达到树最大深度 && 满足题目额外条件
void backtracking(参数) {
if (终止条件) { //常常跟树的深度有关
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { //某一层的宽度
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}77. 组合
题目链接：. - 力扣（LeetCode）
讲解视频：
未优化：带你学透回溯算法-组合问题（对应力扣题目：77.组合）
优化：组合问题的剪枝操作
题目描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
解题思路：
树的宽度：1~n n个数
树的最大深度：k个数组合
额外条件：无
终止条件：找到k个数组合
剪枝：只能往后取数，若从某一位置起其后边的数不能满足题目条件，则直接舍弃。本题中若从某数开始其后数字个数达不到k，则舍弃。即保证for循环中永远都能遍历至k个数，满足i<=n - (k - path.size()) + 1;
代码：
优化版：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void traversal(int n, int k, int startIdx)
{
if(path.size() == k)
{
result.push_back(path);
return;
}
for(int i = startIdx; i <= n - (k - path.size()) + 1; i++)
{
path.push_back(i);
traversal(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
traversal(n,k,1);
return result;
}
};216.组合总和III
题目链接：. - 力扣（LeetCode）
讲解视频：
和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III
题目描述：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了
解题思路：
树的宽度：1~9 9个数
树的最大深度：k个数组合
额外条件：数字和为n
终止条件：数字和为n && 找到k个数组合
剪枝：若数字和大于n，则return；只能往后取数，若从某数开始其后数字个数达不到k，则舍弃。即保证for循环中永远都能遍历至k个数，满足i<=9 - (k - path.size()) + 1;
代码：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void traversal(int k ,int targetSum, int sum, int startIdx)
{
if(sum > targetSum) return;
if(path.size() == k)
{
if(sum == targetSum)
{
result.push_back(path);
return;
}
}
for(int i = startIdx; i <= 10 - (k - path.size()); i++)
{
sum += i;
path.push_back(i);
traversal(k,targetSum,sum,i+1);
path.pop_back();
sum -= i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
traversal(k,n,0,1);
return result;
}
};17.电话号码的字母组合
题目链接：. - 力扣（LeetCode）
讲解视频：
还得用回溯算法！| LeetCode：17.电话号码的字母组合
题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
解题思路：
树的宽度：数字对应字母个数
树的最大深度：输入字符串中数字个数
额外条件：无
终止条件：遍历完字符串中全部数字，即idx == digits.size()
剪枝：无
代码：
class Solution {
private:
string letterMap[10]={
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
public:
vector<string>result;
string s;
void backtracking(const string& digits, int idx)
{
if(idx == digits.size())
{
result.push_back(s);
return ;
}
string letter = letterMap[digits[idx] - '0'];
for(int i = 0; i < letter.size(); i++)
{
s.push_back(letter[i]);
backtracking(digits,idx+1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return result;
backtracking(digits,0);
return result;
}
};39. 组合总和
题目链接：. - 力扣（LeetCode）
讲解视频：
题目描述：
给你一个 无重复元素 的整数数组 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 。 仅有这两种组合。
解题思路：
树的宽度：整数数组candidates的长度
树的最大深度：当前选择数字组合和为target的数字数量
额外条件：无
终止条件：数字组合和为target
剪枝：当和大于target时就return
由于题目中允许一个数可以重复使用，故递归时无需让i+1，仍传i即可
代码：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& candidates, int targetSum, int sum, int idx)
{
if(sum > targetSum) return ;
if(sum == targetSum)
{
result.push_back(path);
return;
}
for(int i = idx; i <candidates.size(); i++)
{
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates,targetSum,sum,i);
path.pop_back();
sum -= candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0,0);
return result;
}
};40.组合总和II
题目链接：. - 力扣（LeetCode）
讲解视频：
回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode: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]]
解题思路：
树的宽度：整数数组candidates的长度
树的最大深度：当前选择数字组合和为target的数字数量
额外条件：无
终止条件：数字组合和为target
分析：横向不能有重复数，纵向可以有重复数（此处重复数是指candidates中不同位置相同的数）
剪枝：当和大于target时就return；先对candidates数组进行排序，之后使用一个used数组标记candidates数组中对应位置数字是否被使用，若candidates[i] == candidates[i-1] && used[i-1] == 0时就不在递归，直接跳转至下一个位置（横向used[i-1]一定为0，纵向used[i-1]一定为1）
代码：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& candidates, int targetSum, vector<int>used, int sum, int idx)
{
if(sum > targetSum) return ;
if(sum == targetSum)
{
result.push_back(path);
return;
}
for(int i = idx; i <candidates.size(); i++)
{
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == 0) continue;
path.push_back(candidates[i]);
sum += candidates[i];
used[i] = 1;
backtracking(candidates,targetSum,used,sum,i+1);
path.pop_back();
sum -= candidates[i];
used[i] = 0;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> used(candidates.size(),0);
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,used,0,0);
return result;
}
};