C++ dfs to find each subset


  • 0
    X

    the time should be O(n^2) or O(nlogn) ? Thanks!

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> result; 
            vector<int> sbset = {}; 
            result.push_back(sbset); 
            if(nums.size()==0) { return result; }
    
    /*=================================================================================================
        V 1.1 : must use dfs, push new and pop_back then take the result(subset) of each step.
        Time:   N^2     Space:  N
    *///===============================================================================================
            vector<int> sub = {}; 
            findSubSet(0, nums, sub, result); // dfs
            return result; 
        }
    private:    // dfs to find subset:
        void findSubSet(int idx, vector<int>& nums, vector<int> sub, vector<vector<int>>& rlt){
            if(idx >= nums.size()) return; 
    
            sub.push_back(nums[idx]);
            rlt.push_back(sub); 
            
            findSubSet(idx+1, nums, sub, rlt);
                
            sub.pop_back();
            findSubSet(idx+1, nums, sub, rlt); 
    
    /*=================================================================================================
        V 1.0 : find sub-set by number of elements, 0-n, yet assuming elements are not the same
        Time:   N^2,    Space:  N
        BUG:    [1,2,3], output: [[],[1,2,3],[2,3],[3]] // missing some cases.
                         expect: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    *///===============================================================================================
    /*        int len = nums.size();
            for(int i = 0; i < len; i++){
                vector<int> subset; 
                for(int j = i; j < len; j++){
                    subset.push_back(nums[j]);
                }
                result.push_back(subset); 
            }
            return result; 
    */        
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.