C++回溯算法中子集問題如何解決

這篇文章主要介紹了C++回溯算法中子集問題如何解決的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++回溯算法中子集問題如何解決文章都會有所收獲，下面我們一起來看看吧。

一、子集

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

體現在代碼上，就是每次遞歸都先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

本題與上題唯一的區別在于：輸入樣例有重復數字，但又要求結果不能重復

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

體現在代碼上，就是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數組記錄每一層元素是否已出現過，其實上一題也能用這種方法，不過上一題沒這個必要

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

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++回溯算法中子集問題如何解決”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。