代码随想录算法训练营Day25 | 216.组合总和III、17.电话号码的字母组合
216.组合总和III
与77.组合差不多，就返回条件中收集结果步骤多了一步判断，同时剪枝策略多了一种
vector<vector<int>> ans;
vector<int> path;
int sum = 0;void backtracking(int num, int& k, int& n) {if (path.size() == k) {if (sum == n)ans.push_back(path);return;}// 剪枝1：同77.组合// 剪枝2：如果当前数已经大于n，那么该循环之后的数必定都大于n，执行剪枝for (int i = num; i <= 9 - (k - path.size()) + 1 && sum + i <= n; ++i) {sum += i;path.push_back(i);backtracking(i + 1, k, n);sum -= i;path.pop_back();}
}vector<vector<int>> combinationSum3(int k, int n) {backtracking(1, k, n);return ans;
}17.电话号码的字母组合
本题与前两题组合的差别：
1、之前的组合是在一个集合中选取元素进行组合，本题是在多个集合中进行组合
2、本题中多了一步从数字映射到字母的操作
因为本题在多个集合中选取元素进行组合，不需要考虑剪枝操作。所以综上来看，理解了映射后其实本题比前两天组合还要简单。
回溯三部曲：
· 参数：
map<int, vector<char>> dict：用于将数字映射到字符数组的哈希表
vector<string>：存放最终结果的全局变量
string path：存放当前路径下组合的字符串（相当于一个一维数组）
int num：本次递归从digits[num]开始搜索
string& digits：题意中的数字字符串
· 终止条件：组合中的元素个数等于digits中的元素个数，说明完成组合，将结果进行保存并返回
· 单层逻辑：
获取当前数字的映射数组
节点操作：当前组合（path）中添加当前值（letter[i]）
递归：获取digits中的下一个数字进行组合（递归参数传入num+1）
回溯：letter[i]在该位置的所有组合已经全部收集完成，将letter[i]弹出当前组合
map<int, vector<char>> dict;
vector<string> ans;
string path;void backtracking(int num, string& digits) {if (path.size() == digits.size()) {ans.push_back(path);return;}vector<char> letters = dict[digits[num] - '0']; // 将字符映射为数组 for (int i = 0; i < letters.size(); ++i) {path.push_back(letters[i]);backtracking(num + 1, digits);path.pop_back();}
}// 相比于之前的组合问题，就多了一步映射的操作
vector<string> letterCombinations(string digits) {dict.insert({ 2, {'a', 'b', 'c'} });dict.insert({ 3, {'d', 'e', 'f'} });dict.insert({ 4, {'g', 'h', 'i'} });dict.insert({ 5, {'j', 'k', 'l'} });dict.insert({ 6, {'m', 'n', 'o'} });dict.insert({ 7, {'p', 'q', 'r', 's'} });dict.insert({ 8, {'t', 'u', 'v'} });dict.insert({ 9, {'w', 'x', 'y', 'z'} });if (digits.empty())return {};backtracking(0, digits);return ans;
}自己还想了一种基于队列的解法：
vector<string> letterCombinations(string digits) {// 创建用于映射的哈希表map<int, vector<char>> dict;dict.insert({ 2, {'a', 'b', 'c'} });dict.insert({ 3, {'d', 'e', 'f'} });dict.insert({ 4, {'g', 'h', 'i'} });dict.insert({ 5, {'j', 'k', 'l'} });dict.insert({ 6, {'m', 'n', 'o'} });dict.insert({ 7, {'p', 'q', 'r', 's'} });dict.insert({ 8, {'t', 'u', 'v'} });dict.insert({ 9, {'w', 'x', 'y', 'z'} });vector<string> ans;// 保存组合过程的队列，初始有一个空字符串queue<string> path;path.push("");string temp;for (int i = 0; i < digits.size(); ++i) {// 获取数字对应的字符数组vector<char> letters = dict[digits[i] - '0'];// 将需要操作的元素取出队列，与字符数组中的字符逐个组合并压入队尾while (path.front().size() == i) {temp = path.front();path.pop();for (char c : letters) {path.push(temp + c);// 当前组合长度等于digits长度时收集结果if (i + 1 == digits.size())ans.push_back(temp + c);}}}return ans;
}