C++回溯算法中子集問題分析探討

更新時間：2023年03月15日 09:13:02 作者：清風何渡

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

一、子集

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

體現(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ū)別在于：輸入樣例有重復數(shù)字，但又要求結(jié)果不能重復

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

體現(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;
    }
};

三、遞增子序列

這題嚴格來說并不是子集問題，但是有一點希望和子集II對比一下，就是同一層元素不能重復的問題，這一題因為元素不能排序，所以在判斷元素是否重復的問題上，并不能采用類似于上一題的if(i>index&&nums[i]==nums[i-1]) continue;方法，而是應該開辟一個used數(shù)組記錄每一層元素是否已出現(xiàn)過，其實上一題也能用這種方法，不過上一題沒這個必要

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

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};//記錄本層元素是否重復使用，新的一層都會重新定義
        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;
    }
};

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

您可能感興趣的文章: