C++回溯算法中子集问题分析探讨

2023-03-15 11:03:38 算法 回溯 子集

一、子集

子集问题与其它问题最大的不同就是：每次递归，不止考虑叶子节点，而是考虑所有节点！

体现在代码上，就是每次递归都先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++回溯算法子集内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

相关文章