本文主要是介绍二刷代码随想录算法训练营第二十五天 | 216.组合总和III 17.电话号码的字母组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、216. 组合总和 III
二、17.电话号码的字母组合
一、216. 组合总和 III
题目链接：力扣
文章讲解：代码随想录
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III
题目：
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
代码：
class Solution {
public:void dfs(vector<vector<int>> &ans, int k, vector<int> &path, int n, int begin, int sum, int num){if (sum > n) return;if (num >= k){if (sum == n)ans.push_back(path);return;}for (int i = begin; i <= 9-(k-num)+1; i++){path[num] = i;dfs(ans, k, path, n, i+1, sum+i, num+1);}return;}vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;vector<int> path(k, 0);dfs(ans, k, path, n, 1, 0, 0);return ans;}
};时间复杂度: O(c(k/M)×k) 空间复杂度O(M)
⏲：5:52
总结：比组合问题多一个限制总和，添加在返回条件部分即可。
二、17.电话号码的字母组合
题目链接：力扣
文章讲解：代码随想录
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合
题目：
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
代码：
class Solution {
public:vector<vector<char>> numbs = {{}, {}, {'a', 'b', 'c'}, {'d','e','f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};void dfs(vector<string> &ans, string path, string &digits, int begin, int end){if (begin == end){ans.push_back(path);return;}int numb = digits[begin]-'0';for (char c : numbs[numb])dfs(ans, path+c, digits, begin+1, end);return;}vector<string> letterCombinations(string digits) {if (digits.empty()) return {};vector<string> ans;string path = "";dfs(ans, path, digits, 0, digits.size());return ans;}
};时间复杂度: O(3^m×4^n) 空间复杂度: O(m+n)
⏲：10:01
总结：本题是多个集合求组合，注意索引是数字的还是字符的。用智能指针更加方便增加字符。
这篇关于二刷代码随想录算法训练营第二十五天 | 216.组合总和III 17.电话号码的字母组合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
