C++数据结构与算法——回溯算法组合问题

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

• 一、77. 组合
• 二、216. 组合总和 III
• 三、17. 电话号码的字母组合
• 四、39. 组合总和
• 五、40. 组合总和 II

一、77. 组合

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        insertVector(n,k,1);
        return result;
    }
    void insertVector(int n,int k,int startIndex){
        if(path.size()==k){
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<=n;i++){
            path.push_back(i);
            insertVector(n,k,i+1);
            path.pop_back();
        }
    }
};

二、216. 组合总和 III

class Solution {
public:
    int targetSum;
    vector<int> path;
    vector<vector<int>> result;
    vector<vector<int>> combinationSum3(int k, int n) {
        insertVector(k,n,1);
        return result;
    }
    void insertVector(int k,int n,int startIndex){
        if(path.size()==k){
            if(targetSum==n){
                result.push_back(path);
                return;
            }
        }
        for(int i=startIndex;i<=9;i++){
            path.push_back(i);
            targetSum+=i;
            insertVector(k,n,i+1);
            path.pop_back();
            targetSum-=i;
        }
    }
};

三、17. 电话号码的字母组合

class Solution {
public:
    vector<string> result;
    string s="";
    string stringV[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> letterCombinations(string digits) {
        insertString(digits,0);
        return result;
    }
    void insertString(string digits,int index){
        if(index==digits.size()){
            // 收获结果
            if(s==""){
                return;
            }
            result.push_back(s);
            return ;
        }
        int digit = digits[index]-'0';
        string nextS = stringV[digit];
        // 遍历
        for(int i=0;i<nextS.size();i++){
            s+= nextS[i];
            insertString(digits,index+1);
            s.pop_back();
        }
    }
};

四、39. 组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int Asum =0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        insertV(candidates,target,0);
        return result;
    }
    void insertV(vector<int> candidates,int target,int startIndex){
        if(Asum==target){
            // 收获结果
            result.push_back(path);
            return;
        }
        else if(Asum>target){
            return;
        }
        for(int i=startIndex;i<candidates.size();i++){
            path.push_back(candidates[i]);
            Asum+=candidates[i];
            insertV(candidates,target,i);
            // 回溯
            path.pop_back();
            Asum-=candidates[i];
        }
    }
};

五、40. 组合总和 II

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int Asum;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 首先进行排序
        sort(candidates.begin(),candidates.end());
        vector<bool> used(candidates.size(),false); // 和candidates等长，并且全为0；
        insertS(candidates,target,0,used);
        return result;
    }
    void insertS(vector<int> candidates,int target,int startIndex,vector<bool> used){
        if(Asum==target){
            result.push_back(path);
            return;
        }
        if(Asum>target){
            return;
        }
        // 用一个used数组表示是否使用过
        for(int i=startIndex;i<candidates.size();i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.push_back(candidates[i]);
            Asum+= candidates[i];
            used[i] = true;
            insertS(candidates,target,i+1,used);
            used[i] =false;
            path.pop_back();
            Asum-= candidates[i];
        }
    }
};