Subsets

Practice Link

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Intuition#

At each element there are exactly two choices — include it in the current subset, or don't. Branching that decision across all n elements gives 2^n leaf calls, one for every possible sequence of include/exclude decisions, and each leaf corresponds to exactly one subset. So plain recursion, without any extra bookkeeping, naturally enumerates the entire power set with no duplicates and no omissions.

That last point matters for the given solution: since nums has unique elements, two different include/exclude sequences can never produce the same subset — there's nothing to deduplicate. So wrapping the results in a set<vector<int>> (as in the code below) buys nothing here; it only adds tree-balancing and vector-comparison overhead on every insert. A plain vector<vector<int>> is both simpler and faster. (The set trick does become genuinely useful on the sibling problem "Subsets II," where nums can contain duplicates and some include/exclude sequences legitimately collide.)

Once you see it as "one binary decision per element," a few other framings fall out naturally: build subsets iteratively by extending every existing subset with the next number (approach 3), or skip the recursion tree entirely and enumerate every n-bit mask directly, since a subset is just an n-bit include/exclude pattern (approach 4).

Approach 1: Recursion (Include/Exclude), as submitted#

class Solution {
public:

    void subsetsUtil(vector<int> &nums, int idx, set<vector<int>> &s, vector<int> &curr){
        if(idx == nums.size())
        {
            s.insert(curr);
            return;
        }

        subsetsUtil(nums, idx+1, s, curr);

        curr.push_back(nums[idx]);
        subsetsUtil(nums, idx+1, s, curr);
        curr.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        set<vector<int>> s;
        vector<int> curr;

        subsetsUtil(nums, 0, s, curr);
        vector<vector<int>> ans(s.begin(), s.end());
        return ans;
    }
};

Time Complexity: O(2^n × n²) — 2^n subsets generated, and each set<vector<int>>::insert costs O(log(2^n)) = O(n) tree comparisons, each comparing subsets element-by-element (O(n)) — overhead that buys nothing since duplicates can't occur.

Space Complexity: O(2^n × n) for the set/output storage, plus O(n) recursion stack depth.

Approach 2: Recursion (Include/Exclude), without the redundant set#

Same logic, but since duplicates are impossible here, push straight into the answer vector.

class Solution {
public:
    void subsetsUtil(vector<int>& nums, int idx, vector<int>& curr, vector<vector<int>>& ans) {
        if (idx == nums.size()) {
            ans.push_back(curr);
            return;
        }

        subsetsUtil(nums, idx + 1, curr, ans);        // exclude nums[idx]

        curr.push_back(nums[idx]);
        subsetsUtil(nums, idx + 1, curr, ans);         // include nums[idx]
        curr.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr;
        subsetsUtil(nums, 0, curr, ans);
        return ans;
    }
};

Time Complexity: O(2^n × n) — 2^n subsets, each copied into ans at cost O(n) (average subset length is n/2, so total copy work is O(2^n × n)).

Space Complexity: O(2^n × n) for the output, plus O(n) recursion stack depth.

Approach 3: Backtracking (start-index style)#

A different but equally common framing: at each recursive call, immediately record the current subset (it's always valid), then extend it by trying every number from start onward.

class Solution {
public:
    void backtrack(vector<int>& nums, int start, vector<int>& curr, vector<vector<int>>& ans) {
        ans.push_back(curr);
        for (int i = start; i < nums.size(); i++) {
            curr.push_back(nums[i]);
            backtrack(nums, i + 1, curr, ans);
            curr.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr;
        backtrack(nums, 0, curr, ans);
        return ans;
    }
};

Time Complexity: O(2^n × n) — same subset count and copy cost as approach 2, just organized as "extend forward" instead of "include/exclude."

Space Complexity: O(2^n × n) for the output, plus O(n) recursion stack depth.

Approach 4: Iterative (build up subset-by-subset)#

Start with just the empty subset. For each new number, take every subset built so far and create a new copy with that number appended — this doubles the answer list at each step, which is exactly how 2^n subsets get built up over n numbers.

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans = {{}};
        for (int num : nums) {
            int size = ans.size();
            for (int i = 0; i < size; i++) {
                vector<int> subset = ans[i];
                subset.push_back(num);
                ans.push_back(subset);
            }
        }
        return ans;
    }
};

Time Complexity: O(2^n × n) — the answer list doubles n times, and each new subset is a copy costing up to O(n).

Space Complexity: O(2^n × n) for the output; no recursion stack.

Approach 5: Bitmasking#

A subset is just an n-bit pattern of include/exclude decisions, so enumerate every integer mask from 0 to 2^n - 1 and read off bit i to decide whether nums[i] is included.

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        for (int mask = 0; mask < (1 << n); mask++) {
            vector<int> subset;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i))
                    subset.push_back(nums[i]);
            }
            ans.push_back(subset);
        }
        return ans;
    }
};

Time Complexity: O(2^n × n) — 2^n masks, each requiring an O(n) scan over bits.

Space Complexity: O(2^n × n) for the output; O(1) extra space (no recursion, no intermediate copies beyond the current subset).