LeetCode77. 组合
https://leetcode-cn.com/problems/combinations/
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
思路
回溯模板：
void backtracking(选择列表，路径，结果)
{
if (终止条件)
{
存放结果;
return;
}
//控制树的横向遍历
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表，路径，结果); //递归：控制树的纵向遍历
回溯，撤销处理结果
}
}
所有用回溯解决的问题都可以抽象为树形结构：
回溯三部曲：
1.递归函数的返回值和参数
定义两个全局变量，一个用来存放符合条件的路径path，一个用来存放所有符合条件的路径的结果集合result。
函数里一定有两个参数：集合n里面取k个数的组合，那么n和k是函数的两个int型参数。
还有一个int型参数startIndex，这个参数用来记录本层递归中，选择列表从哪里开始遍历（选择列表就是[1,…,n] ）。随着递归控制树的纵向遍历，可选择的范围进而收缩，调整可选择的范围，就是要靠startIndex。例如，在上图中，在集合[1,2,3,4]取1之后，下一层递归就要从[2,3,4]中取数了，那么下一层递归如何知道要从[2,3,4]中取数呢，就是要靠startIndex来记录下一层递归搜索的起始位置。
vector<int> path; //存放符合条件的路径
vector<vector<int>> result; //存放所有符合条件的路径的结果集合
void backtrack(int n, int k, int startIndex)
2.递归函数的终止条件
path的大小如果达到k，那么就说明我们找到一个大小为k的组合了，在上图中path存的就是根节点到叶子节点的路径。此时用result把path保存起来，并终止本层递归返回。
if (path.size() == k)
{
result.push_back(path);
return;
}
3.搜索过程
我们定义的backtrack函数其实就像一个指针，在树中游走同时正确维护每个节点的属性。每当走到叶子节点(即碰到递归函数的终止条件)，就保存符合条件的路径，返回并回溯。
//控制树的横向遍历
for (int i = startIndex; i <= n; ++i)
{
path.push_back(i);
backtrack(n, k, i + 1); //递归：控制树的纵向遍历
path.pop_back();
}
代码
class Solution
{
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(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);
backtrack(n, k, i + 1); //递归：控制树的纵向遍历
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k)
{
backtrack(n, k, 1);
return result;
}
}
LeetCode39. 组合总和
https://leetcode-cn.com/problems/combination-sum/
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
思路
回溯模板：
void backtracking(选择列表，路径，结果)
{
if (终止条件)
{
存放结果;
return;
}
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表，路径，结果);
回溯，撤销处理结果
}
}
所有用回溯解决的问题都可以抽象为树形结构：
回溯三部曲：
1.递归函数的返回值和参数
定义两个全局变量，一个用来存放符合条件的路径path，一个用来存放所有符合条件的路径的结果集合result。
函数里一定有两个参数：选择列表(数组candidates)和目标值(int型参数target)。
还有一个int型变量来sum统计path里的元素总和
还有一个int型参数startIndex，这个参数用来记录本层递归的中，选择列表从哪里开始遍历（选择列表就是数组candidates）。随着递归控制树的纵向遍历，可选择的范围进而收缩，调整可选择的范围，就是要靠startIndex。
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(vector<int>& candidates, int target, int sum, int startIndex)
2.递归函数的终止条件
终止条件有两种情况，sum大于target和sum等于target。
sum等于target的时候，需要收集path。
if (sum > target) return;
if (sum == target)
{
result.push_back(path);
return;
}
3.搜索过程
我们定义的backtrack函数其实就像一个指针，在树中游走同时正确维护每个节点的属性。每当走到叶子节点(即碰到递归函数的终止条件)，就保存符合条件的路径，返回并回溯。
//控制树的横向遍历
for (int i = startIndex; i < size && sum + candidates[i] <= target; ++i)
{
sum = sum + candidates[i];
path.push_back(candidates[i]);
//用i而不用i + 1, 表示可选重复元素
backtrack(candidates, target, sum, i); //递归：控制树的纵向遍历
sum = sum - candidates[i];
path.pop_back();
}
代码
class Solution
{
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(vector<int>& candidates, int target, int sum, int startIndex)
{
int size = candidates.size();
if (sum > target) return;
if (sum == target)
{
result.push_back(path);
return;
}
//控制树的横向遍历
for (int i = startIndex; i < size && sum + candidates[i] <= target; ++i)
{
sum = sum + candidates[i];
path.push_back(candidates[i]);
//用i而不用i + 1, 表示可重复选元素
backtrack(candidates, target, sum, i); //递归：控制树的纵向遍历
sum = sum - candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
sort(candidates.begin(), candidates.end());
backtrack(candidates, target, 0, 0);
return result;
}
};
LeetCode40. 组合总和II
https://leetcode-cn.com/problems/combination-sum-ii/
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
思路
回溯模板：
void backtracking(选择列表，路径，结果)
{
if (终止条件)
{
存放结果;
return;
}
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表，路径，结果);
回溯，撤销处理结果
}
}
本题与LeetCode39. 组合总和有两个区别：
- 本题candidates 中的每个数字在每个组合中只能使用一次。
- 本题数组candidates的元素是有重复的，但不能有重复的组合。
所以本题的大体思路与LeetCode39. 组合总和是相同的，重点是要去重。所谓去重，其实就是使用过的元素不能重复选取。
用回溯解决的问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
根据题意：元素在同一个组合内是可以重复的，但两个组合不能相同。同一树层上的是两个组合里的元素，所以我们要去重的是同一树层上的“使用过”；而同一树枝上的都是一个组合里的元素，所以不用去重。
要在代码层面实现以上的去重逻辑，就需要先对数组进行排序，然后定义一个bool类型数组used。这个数组的元素初始值都为false表示对应的candidate的元素都没被访问过。如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]，此时for循环里应该做continue的操作。
所有用回溯解决的问题都可以抽象为树形结构：
代码
class Solution
{
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used)
{
int sz = candidates.size();
if (sum > target) return;
if (sum == target)
{
result.push_back(path);
return;
}
//控制树的横向遍历
for (int i = startIndex; i < sz && sum + candidates[i] <= target; ++i)
{
if (i >= 1 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
{
continue;
}
used[i] = true;
sum = sum + candidates[i];
path.push_back(candidates[i]);
//用i + 1而不用i, 表示不可重复选元素
backtrack(candidates, target, sum, i + 1, used); //递归：控制树的纵向遍历
used[i] = false;
sum = sum - candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
{
sort(candidates.begin(), candidates.end());
//used数组存放bool类型的元素，初始值都为false表示数组nums的元素都没被访问过
vector<bool> used(candidates.size(), false);
backtrack(candidates, target, 0, 0, used);
return result;
}
};
LeetCode216. 组合总和III
https://leetcode-cn.com/problems/combination-sum-iii/
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
输入: k = 3, n = 7
输出: [[1,2,4]]
思路
回溯模板：
void backtracking(选择列表，路径，结果)
{
if (终止条件)
{
存放结果;
return;
}
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表，路径，结果);
回溯，撤销处理结果
}
}
所有用回溯解决的问题都可以抽象为树形结构：
回溯三部曲：
1.递归函数的返回值和参数
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(int k, int n, int sum, int startIndex)
2.递归函数的终止条件
if (sum > n) return;
if (path.size() == k)
{
if (sum == n) result.push_back(path);
return;
}
3.搜索过程
我们定义的backtrack函数其实就像一个指针，在树中游走同时正确维护每个节点的属性。每当走到叶子节点(即碰到递归函数的终止条件)，就保存符合条件的路径，返回并回溯。
//控制树的横向遍历
for (int i = startIndex; i <= 9 && sum + i <= n; ++i)
{
sum = sum + i;
path.push_back(i);
backtrack(k, n, sum, i + 1); //递归：控制树的纵向遍历
sum = sum - i;
path.pop_back();
}
}
代码
class Solution {
private:
vector<vector<int>> result; //存放所有符合条件的路径的结果集合result
vector<int> path; //存放符合条件的路径path
void backtrack(int k, int n, int sum, int startIndex)
{
if (sum > n) return;
if (path.size() == k)
{
if (sum == n) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9 && sum + i <= n; ++i)
{
sum = sum + i;
path.push_back(i);
backtrack(k, n, sum, i + 1);
sum = sum - i;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n)
{
backtrack(k, n, 0, 1);
return result;
}
};
LeetCode17. 电话号码的字母组合
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"
思路
回溯模板：
void backtracking(选择列表，路径，结果)
{
if (终止条件)
{
存放结果;
return;
}
for (在选择列表中选择)
{
处理节点;
backtracking(选择列表，路径，结果);
回溯，撤销处理结果
}
}
所有用回溯解决的问题都可以抽象为树形结构：
回溯三部曲：
1.递归函数的返回值和参数
定义两个全局变量，一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来。
函数里一定有一个参数：字符串digits，
还有一个int型参数index。注意这个index可不是前面几题的startIndex了，这个index是记录遍历第几个数字了，就是用来遍历字符串digits的，同时index也表示树的深度。
vector<string> result;
string s;
void backtrack(const string& digits, int index)
2.递归函数的终止条件
如果index 等于字符串digits的长度(本来index就是用来遍历字符串digits的)，那么就收集结果，结束本层递归。
if (index == digits.size())
{
result.push_back(s);
return;
}
3.搜索过程
首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。
然后for循环来处理这个字符集，注意这里的for循环，不像是在前面几题中是从startIndex开始遍历的，因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而前面几题都是是求同一个集合中的组合。
int digit = digits[index] - '0';
string letters = numToString[digit];
for (int i = 0; i < letters.size(); ++i)
{
s.push_back(letters[i]);
backtrack(digits, index + 1);
s.pop_back();
}
代码
class Solution
{
private:
const vector<string> numToString =
{
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
vector<string> result;
string s;
void backtrack(const string& digits, int index)
{
if (index == digits.size())
{
result.push_back(s);
return;
}
int digit = digits[index] - '0';
string letters = numToString[digit];
for (int i = 0; i < letters.size(); ++i)
{
s.push_back(letters[i]);
backtrack(digits, index + 1);
s.pop_back();
}
}
public:
vector<string> letterCombinations(string digits)
{
if (digits.size() == 0) return result;
backtrack(digits, 0);
return result;
}
};