# C++ dfs to find each subset

• 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;
*/
}
};
``````

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