C++回溯算法中組合的相關(guān)問(wèn)題怎么解決

這篇文章主要講解了“C++回溯算法中組合的相關(guān)問(wèn)題怎么解決”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“C++回溯算法中組合的相關(guān)問(wèn)題怎么解決”吧！

回溯算法模板

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }
    for (選擇：本層集合中元素（樹(shù)中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? {
        處理節(jié)點(diǎn);
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷(xiāo)處理結(jié)果
    }
}

回溯問(wèn)題，最關(guān)鍵的是畫(huà)出二叉樹(shù)，遍歷、剪枝問(wèn)題都要通過(guò)直觀的觀察才能總結(jié)

一、組合

剪枝策略

已經(jīng)選擇的元素個(gè)數(shù)：path.size();

還需要的元素個(gè)數(shù)為: k - path.size();

在集合n中至多要從該起始位置 : n - (k - path.size()) + 1，開(kāi)始遍歷

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

二、組合總和III與組合總和

1.組合總和III

在組合的基礎(chǔ)上，多了一個(gè)求和的操作，求和也可以剪枝

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

2.組合總和

本題與組合III的區(qū)別在于，不限制組合內(nèi)數(shù)字的個(gè)數(shù)，且同一個(gè)數(shù)字可以無(wú)限制重復(fù)被選取，體現(xiàn)在代碼上就是，向下遞歸的時(shí)候，i不變

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates, int target,int index,int sum){
        if(sum>target) return;
        if(sum==target){
            result.push_back(path);
            return;
        }
        for(int i=index;i<candidates.size();i++){
            path.push_back(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates,target,i,sum);
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};

3.組合總和II

本題和組合總和的區(qū)別在于，輸入樣例中含有重復(fù)元素時(shí)，輸出樣例不能有重復(fù)元素

同一條枝干上，元素可以相同；而不同的枝干則不能重復(fù)

即：橫向遍歷不能重復(fù)、縱向遍歷可以重復(fù)

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& candidates, int target,int index,int sum){
        if(sum>target) return;
        if(sum==target){
            result.push_back(path);
            return;
        }
        for(int i=index;i<candidates.size();i++){
            if(i>index&&candidates[i]==candidates[i-1])
                continue;
            path.push_back(candidates[i]);
            sum+=candidates[i];
            backtracking(candidates,target,i+1,sum);
            sum-=candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};

三、電話號(hào)碼的字母組合

這題很好的考察了：for循環(huán)橫向遍歷、遞歸縱向遍歷的知識(shí)點(diǎn)

class Solution {
private:
    const string letterMap[10]={
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
public:
    string path;
    vector<string> result;
    void backtracking(string digits,int index){
        if(index==digits.size()){
            result.push_back(path);
            return;
        }
        int digit=digits[index]-'0';
        string letter=letterMap[digit];
        for(int i=0;i<letter.size();i++){
            path.push_back(letter[i]);
            backtracking(digits,index+1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return result;
        backtracking(digits,0);
        return result;
    }
};

感謝各位的閱讀，以上就是“C++回溯算法中組合的相關(guān)問(wèn)題怎么解決”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)C++回溯算法中組合的相關(guān)問(wèn)題怎么解決這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！