代码随想录算法训练营Day24|216.组合总和III、17.电话号码的字母组合

组合总和III

216. 组合总和 III - 力扣（LeetCode）

        思路和昨日的组合题类似，但注意对回溯算法中，收获时的条件需要写对，path的长度要为k的同时，path中元素总和要为n。

class Solution {
public:vector<int> path;vector<vector<int>> paths;int sum = 0; // 维护当前路径的和void backtracking(int k, int n, int startindex) {if (path.size() == k && sum == n) {paths.push_back(path);return;}for (int i = startindex; i <= 9; i++) {path.push_back(i);sum += i; // 更新路径和backtracking(k, n, i + 1);sum -= i; // 回溯时，恢复路径和path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {backtracking(k, n, 1);return paths;}
};

算法的时间复杂度，在最差的情况需，我们需要生成所有C(9,n)个组合，并且对于每个组合，都需要进行k层递归，因此时间复杂度为O(C(9,n)*n)。

空间复杂度考虑递归栈，递归栈的最大深度为n，每个组合需要n个元素的存储空间，隐形空间复杂度是O(n)。

电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

首先，考虑使用一个哈希表来存储数值（这里用数值方便些，之后用 i - '0'可以将char转换为整形）与字符的映射关系。

具体参考代码随想录 (programmercarl.com)

回溯三步法

1.确定回溯函数参数，我们每次回溯返回的值都会存放在一个path字符串中，并存在一个paths数组存放所有的组合结果中，我们用全局变量表示，此外，我们还需要一个变量index来指示现在遍历的位置。

2.确认终止条件。当index与需要遍历的字符长度相同时，就将值存入path中，并返回。

3.单层遍历逻辑，我们需要知道在当前index下的umap存储的字符串大小，然后对这个字符串中的字符进行递归遍历。之后对下一个字符进行处理，因为本题是求不同集合间的组合。

整体代码

class Solution {
public:vector<string> paths; // 用于存储所有可能的字母组合string path; // 用于存储当前的字母组合unordered_map<int, vector<char>> umap; // 创建一个映射表，将数字映射到对应的字母Solution() {umap[2] = {'a', 'b', 'c'}; // 数字2对应的字母umap[3] = {'d', 'e', 'f'}; // 数字3对应的字母umap[4] = {'g', 'h', 'i'}; // 数字4对应的字母umap[5] = {'j', 'k', 'l'}; // 数字5对应的字母umap[6] = {'m', 'n', 'o'}; // 数字6对应的字母umap[7] = {'p', 'q', 'r', 's'}; // 数字7对应的字母umap[8] = {'t', 'u', 'v'}; // 数字8对应的字母umap[9] = {'w', 'x', 'y', 'z'}; // 数字9对应的字母}void backtracking(const string& digits, int index) {// 如果当前组合的长度等于输入数字的长度，将当前组合添加到结果中if (index == digits.size()) {paths.push_back(path);return;}// 将当前处理的数字转换为对应的映射表中的字母int digit = digits[index] - '0'; // 遍历映射表中的字母，进行回溯for (int i = 0; i < umap[digit].size(); i++) {path.push_back(umap[digit][i]); // 添加字母到当前组合backtracking(digits, index + 1); // 处理下一个数字path.pop_back();}}vector<string> letterCombinations(string digits) {//输入为空，直接返回空的结果if (digits.empty()) {return paths;}backtracking(digits, 0);return paths;}
};

算法的时间复杂度参考在最坏情况下，每个数字对应最多4个字母，若输入数字的长度为n，则最坏情况下时间复杂度为O(4^n)，因为每一步都有4种选择。代码随想录上是将3个字母和4个字母都区分了出来所以是O(3^m*4^n)

空间复杂度由两部分组成，一是递归的栈空间，二是存储结果的空间，栈空间最坏情况下与输入数字长度n成正比O(n)。存储空间取决于可能的组合数量，最坏情况下为O(4^n)，总的空间复杂度为O（m+4^n）。