回溯算法
77. 组合
题意：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
示例：
思路：本题的思想，主要是利用回溯的思想，先固定tmp插入的个数为k，当检测到tmp的大小等于k时，直接加入到我们的存储组合数组arr中，这时回溯一趟的结束条件；然后是遍历过程，定义一个起始位置，加入组合中，递归函数，不断添加新的元素进入组合中，再插入arr中，插入完一次，说明最后一个元素使用结束，移除在加入下一个元素，重复循环，直到所有组合存储完毕，返回arr
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
void ComArr(int n,int k,int begin)
{
if(tmp.size()==k)
{
arr.push_back(tmp);
return;
}
for(int i=begin;i<=n;i++)
{
tmp.push_back(i);
ComArr(n,k,i+1);
tmp.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
ComArr(n,k,1);
return arr;
}216. 组合总和 III
题意：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例：
思路：本题和上一道题的思路几乎一模一样，只是有两点不同：
- 组合数的范围在1到9之间，并不是1到n
- 每次回溯终止条件，只要满足tmp的大小等于k就必须返回，无论数组和是否等于n
C++代码：
vector<vector<int>> arr;
vector<int> tmp;
int SumArr(vector<int> ss)//对数组进行累加
{
int sum=0;
for(auto e:ss)
{
sum+=e;
}
return sum;
}
void ComSumArr(int k,int n,int begin)
{
if(tmp.size()==k)//回溯终止条件，无论数组和是否等于n，都必须返回；等于n，先插入arr中，再返回
{
if(SumArr(tmp)==n)
{
arr.push_back(tmp);
}
return;
}
for(int i=begin;i<=9;i++)//严格限制组合数的范围
{
tmp.push_back(i);
ComSumArr(k,n,i+1);
tmp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
ComSumArr(k,n,1);
return arr;
}17. 电话号码的字母组合
题意：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
思路：本题的思路就是先列举出每个数字对应的字母集合，然后将数字对应的第一个字母写入集合中，直到最后一个数字，才开始进行回溯算法，就像二叉树的后序遍历一样，从叶子开始一个个组合，再到上一层，这样循环组合
C++代码：
string sum[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//这里对应了0~9数字的字母
vector<string> arr;
string tmp;
void ComStrArr(string digits,int begin)
{
if(tmp.size()==digits.size())//只要tmp大小等于digits大小，就说明可以存入了
{
arr.push_back(tmp);
return;
}
int Num=digits[begin]-'0';
string SumNum=sum[Num];//将一个数字对应的字母集合对应起来
for(int i=0;i<SumNum.size();i++)//开始回溯组合
{
tmp.push_back(SumNum[i]);
ComStrArr(digits,begin+1);
tmp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size()==0)
{
return arr;
}
ComStrArr(digits,0);
return arr;
}