代码随想录训练营Day18 | 77. 组合 - 216.组合总和III - 17.电话号码的字母组合

77. 组合

• 题目链接：77. 组合
• 思路：回溯算法，倒着选择1~n中的数，倒着选择的特殊性在于，选择的数就是剩下的可选择的数的数量，所以每次选择的数要比剩下需要选择的数的数量多才行
• 代码：

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> path;auto dfs = [&](auto&& dfs, int i) {int d = k - path.size(); // 还需要选择的数的数量if(d == 0) { // 成功ans.push_back(path); return;}// 倒着选择的特殊性，选择的数要比剩下需要选择的数量大for(int j = i; j >= d; j--) { path.push_back(j);dfs(dfs, j - 1);path.pop_back();}};dfs(dfs, n); // 从n开始选择return ans;}
};

216.组合总和III

• 题目链接：216.组合总和III
• 思路：
  1. 同上一道组合题一样的思路，不过这里需要和为n，选择的数在[1, 9]之间，仍然是倒着选，当选择的数量为k，并且和为n时，即为符合答案；
  2. 剪枝优化，这里剪枝优化的关键点在于，剩下还需要选d个数，倒着选，剩下选择的数的范围是[1, i]，如果 i + (i - 1) + (i - 2)… + (i - d + 1) = (2 * i - d + 1) / 2，等差数列和公式，即最大的d个数，的和加起来都没有，再加上之前选择的数的值的和都达不到目标值，就可以不继续往下递归；
• 代码：

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;vector<int> path;auto dfs = [&](auto&& dfs, int i, int t) {int d = k - path.size(); // 还要选 d 个数if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝优化return;}// 这是t 只能是 >= 0, d >= 0if (d == 0) { // 找到一个合法组合ans.emplace_back(path);return;}for (int j = i; j >= d; j--) {path.push_back(j);dfs(dfs, j - 1, t - j);path.pop_back();}};dfs(dfs, 9, n);return ans;}
};

17.电话号码的字母组合

• 题目链接：17.电话号码的字母组合
• 思路：
  1. 这道题思路依然和组合差不多，仍然是选择，不过这里根据数去选择对应的字符，所以需要有一个数和字符的对应表，先用map创建对应的数和字符对应表；
  2. 每次根据digits，对应位置中的数字，选择这个数字对应的字符集中的一个，满足情况加入到结果列表即可
• 代码：

class Solution {
public:vector<string> letterCombinations(string digits) {unordered_map<int, string> kv = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}}; // 创建对应表vector<string> ans;if(digits.empty()) // 字符串为空没有情况return ans;string tmp;int n = digits.length(); // 选择的长度auto dfs = [&](auto&& dfs, int i) {if(i == n) { // 长度为n，加入到结果中ans.push_back(tmp);return;}for(char c : kv[digits[i] - '0']) { // 每次选择数字对应字符集中的一个tmp.push_back(c);dfs(dfs, i+1);tmp.pop_back();}};dfs(dfs, 0); // 从第一个开始return ans;}
};