216. 组合总和 III
题目：https://leetcode.cn/problems/combination-sum-iii/
算法思想：
回溯的方法。
回溯本质上是使用递归的方法实现多层for循环。
回溯在return的时候首个结果。
for循环中加入数值和弹出数值
class Solution {
public:
vector<vector<int>> output;
vector<int> path;
int sum = 0;
void huisu(int n, int k, int start)
{
if(sum > n || path.size()>k)
return;
if(path.size()==k && sum == n)
{
output.push_back(path);
return;
}
for(int i=start;i<=(9-(k-path.size()))+1;i++)
{
// if(i > (10-k))
// return;
path.push_back(i);
sum = sum+i;
// cout<<"sum:"<<sum<<endl;
huisu(n,k, i+1);
path.pop_back();
sum = sum-i;
}
return;
}
vector<vector<int>> combinationSum3(int k, int n) {
huisu(n,k,1);
return output;
}
};
17. 电话号码的字母组合
题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
算法思想：
首先想好for循环怎么实现，再转化为for循环实现。
代码：
class Solution {
public:
vector<string> output;
string path = "";
void huisu(vector<string>& data, int i)
{
if(i == data.size())
{
if(path == "")
return;
output.push_back(path);
return;
}
for(int j=0;j<data[i].size();j++)
{
string tmp = path;
path = path+data[i][j];
huisu(data, i+1);
path = path+data[i][j];
path = tmp;
}
}
vector<string> letterCombinations(string digits) {
unordered_map<int,string> m;
m['2'] = "abc";
m['3'] = "def";
m['4'] = "ghi";
m['5'] = "jkl";
m['6'] = "mno";
m['7'] = "pqrs";
m['8'] = "tuv";
m['9'] = "wxyz";
vector<string> data;
for(int i=0;i<digits.size();i++)
data.push_back(m[digits[i]]);
huisu(data, 0);
return output;
}
};
