Clean DFS Solution in C++ O(2^n)


  • 0
    U

    The idea is simple : At every step (index), there are two possibilities: either the element at that index is a part of the subset OR it is not a part of the subset. So I make two recursive calls: first one skips the current element and the second one includes it.

    class Solution {
    public:
        void findSubsets(int i, vector<int> &nums, vector<int> &cur, vector<vector<int> > & ans)
        {
            if(i == nums.size())
            {
                ans.push_back(cur);
                return;
            }
            
            findSubsets(i+1, nums, cur, ans);
            cur.push_back(nums[i]);
            findSubsets(i+1, nums, cur, ans);
            cur.pop_back();
        }
        
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<int> cur;
            vector<vector<int> > ans;
            findSubsets(0, nums, cur, ans);
            return ans;
        }
    };
    

Log in to reply
 

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