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

发布时间:2024年01月07日

216. 组合总和 III

可以参考77.组合中关于选取数组的相关操作。

递归函数的返回值以及参数:一般为void类型

递归函数终止条件:path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,然后当n为0的时候(找到数组值为n),终止,将结果导入res中

递归函数单层逻辑:回溯法的搜索过程就是一个树型结构的遍历过程,for循环用来横向遍历,递归的过程是纵向遍历。

class Solution {
public:
    vector<vector<int>>res;
    void backtracing(vector<int>path,int k,int n,int index){
        if(path.size()==k&&!n){
            res.push_back(path);
            return;
        }
        for(int i=index;i<=9;i++){
            path.push_back(i);
            n-=i;
            backtracing(path,k,n,i+1);
            n+=i;
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int>path;
        int index=1;
        backtracing(path,k,n,index);
        return res;
    }
};

剪枝操作

如果n为负了,就没有再继续减下去的必要了,可以提前回溯。

 for(int i=index;i<=9-(k-path.size())+1;i++){
            path.push_back(i);
            n-=i;

            //提前回溯
            if(n<0){
                n+=i;
                path.pop_back();
                return;
            }
            backtracing(path,k,n,i+1);
            n+=i;
            path.pop_back();
        }

?完整代码:

class Solution {
public:
    vector<vector<int>>res;
    void backtracing(vector<int>path,int k,int n,int index){
        if(path.size()==k&&!n){
            res.push_back(path);
            return;
        }
        for(int i=index;i<=9-(k-path.size())+1;i++){
            path.push_back(i);
            n-=i;
            if(n<0){
                n+=i;
                path.pop_back();
                return;
            }
            backtracing(path,k,n,i+1);
            n+=i;
            path.pop_back();
        }

    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int>path;
        int index=1;
        backtracing(path,k,n,index);
        return res;
    }
};

17. 电话号码的字母组合

遇到回溯的题目,首先可以尝试画一下n叉树

确定回溯函数参数:首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。

确定终止条件:到达叶子结点是搜索,即stringg s的长度要与原先输入的长度相等

确定单层遍历逻辑:首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。然后for循环来处理这个字符集。

class Solution {
public:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    vector<string> res;
    string s;
    void backtracing(string digits,int index){
        if(index==digits.size()){
            res.push_back(s);
            return;
        }
        int num=digits[index]-'0';
        string letter=letterMap[num];
        for(int i=0;i<letter.size();i++){
            s.push_back(letter[i]);
            backtracing(digits,index+1);
            s.pop_back();
        }

    }
    vector<string> letterCombinations(string digits) {
        int index=0;
        if(!digits.size()) return res;
        backtracing(digits,index);
        return res;
    }
};

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