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

2024-01-10 06:29:52

216.组合总和III

题目链接:216.组合总和III

找出所有相加之和为 nk 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

文章讲解/视频讲解:https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html

思路

首先确定回溯的函数参数,参数包括当前的组合path,当前遍历到的数字cur,组合的目标大小k,以及当前组合的总和与目标数字n的差值left。

什么时候回溯结束?当然是当前组合path的大小等于k的时候,这时判断一下left是否等于0,如果等于0则把当前path添加到结果中。

如何遍历?在当前的回溯中,依次从cur往后遍历,如果遍历的数i大于left或者大于9则停止。同时,递归地对添加的下一个数进行处理,此时的left值为left - i。

这里有一个要注意的点,数字只能在1到9之间。

C++实现

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> path;
        backtracking(path, 1, k, n);
        return results;
    }

    void backtracking(vector<int>& path, int cur, int k, int left){
        if(path.size() == k){
            if(left == 0) results.push_back(path);
            return;
        }
        for(int i = cur;i<=left && i<=9;i++){
            path.push_back(i);
            backtracking(path, i + 1, k, left - i);
            path.pop_back();
        }
    }
};

17.电话号码的字母组合

题目链接:17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

文章讲解/视频讲解:https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

思路

采用回溯来解决该问题,首先分析一下这道题的回溯架构。回溯分为横向和纵向两个方向的搜索,对于这道题来说,横向就是对当前数字i对应的字母映射的搜索,纵向则是对于输入的数字字符串的搜索。

依然按照回溯的三部曲进行分析。

回溯的函数参数?参数应该包括当前的字母组合path,当前遍历到的数字字符串下标cur,以及对于数字字符串digits的引用。

回溯什么时候结束?当数字字符串下标cur等于digits的长度的时候,表示已经遍历到了digits字符串的末尾。

如何进行遍历?在横向搜索过程中,依次遍历当前数字对应的字母列表,在每一次的遍历过程中,递归地对cur + 1的数字字符串下标进行纵向搜索。

C++实现

class Solution {
public:
    vector<string> results;
    vector<string> digitMaps;

    vector<string> letterCombinations(string digits) {
        digitMaps = {"0", "0", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string path;
        backtracking(path, 0, digits);
        return results;
    }

    void backtracking(string& path, int cur, const string& digits){
        if(cur == digits.size()){
            if(path != "") results.push_back(path);
            return;
        }
        int num = digits[cur] - '0';
        for(int i = 0;i<digitMaps[num].size();i++){
            path.push_back(digitMaps[num][i]);
            backtracking(path, cur + 1, digits);
            path.pop_back();
        }
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135431720
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。