C++回溯算法中子集問(wèn)題如何解決

這篇文章主要介紹了C++回溯算法中子集問(wèn)題如何解決的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇C++回溯算法中子集問(wèn)題如何解決文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。

一、子集

子集問(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)題上，并不能采用類似于上一題的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)題如何解決”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“C++回溯算法中子集問(wèn)題如何解決”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。