C++回溯算法中子集問(wèn)題分析探討

更新時(shí)間：2023年03月15日 09:13:02 作者：清風(fēng)何渡

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿(mǎn)足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱(chēng)為回溯點(diǎn)

一、子集

子集問(wèn)題與其它問(wèn)題最大的不同就是：每次遞歸，不止考慮葉子節(jié)點(diǎn)，而是考慮所有節(jié)點(diǎn)！

體現(xiàn)在代碼上，就是每次遞歸都先result.push_back(path);

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

二、子集II

本題與上題唯一的區(qū)別在于：輸入樣例有重復(fù)數(shù)字，但又要求結(jié)果不能重復(fù)

本題與組合總和II是一個(gè)套路，即：橫向遍歷不可重復(fù)，縱向遍歷可重復(fù)

體現(xiàn)在代碼上，就是if(i>index&&nums[i]==nums[i-1]) continue;

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

三、遞增子序列

這題嚴(yán)格來(lái)說(shuō)并不是子集問(wèn)題，但是有一點(diǎn)希望和子集II對(duì)比一下，就是同一層元素不能重復(fù)的問(wèn)題，這一題因?yàn)樵夭荒芘判?，所以在判斷元素是否重?fù)的問(wèn)題上，并不能采用類(lèi)似于上一題的if(i>index&&nums[i]==nums[i-1]) continue;方法，而是應(yīng)該開(kāi)辟一個(gè)used數(shù)組記錄每一層元素是否已出現(xiàn)過(guò)，其實(shí)上一題也能用這種方法，不過(guò)上一題沒(méi)這個(gè)必要

還要注意used數(shù)組開(kāi)辟的位置是在backtracking函數(shù)內(nèi)部，意思很明顯：used數(shù)組只管記錄本層元素，至于下一層元素，則要開(kāi)辟新的ued數(shù)組來(lái)記錄

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums,int index){
        if(path.size()>1){
            result.push_back(path);
            if(index==nums.size()) return;
        }
        int used[201]={0};//記錄本層元素是否重復(fù)使用，新的一層都會(huì)重新定義
        for(int i=index;i<nums.size();i++){
            if(used[nums[i]+100]==1||(!path.empty()&&nums[i]<path.back()))
                continue;
            used[nums[i]+100]=1;
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

到此這篇關(guān)于C++回溯算法中子集問(wèn)題分析探討的文章就介紹到這了,更多相關(guān)C++回溯算法子集內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: