75. Subsets

Each number x doubles the answer: every existing subset gives birth to a new subset that includes x. Start with [[]] (the only subset containing none of the elements yet) and at each step union the current list with copies of itself extended by the new number.

Why doubling is correct

The set of all subsets of nums = [a, b, c, ...] can be partitioned into:

1. Subsets that don't contain the last element (these are the subsets of the prefix without the last element).
2. Subsets that do contain the last element (each is the previous subset plus the last element).

So if we know all subsets of nums[:-1], we get all subsets of nums by combining (1) those subsets and (2) those subsets each extended by nums[-1]. Inductively, build up from the empty set.

Steps

1. Initialise result = [[]] (the empty subset is always included).
2. For each x in nums:
   • For every subset sub currently in result, also add sub + [x] to result.
3. Return result.

Walk-through

nums = [1, 2, 3]:

That's 2³ = 8 subsets — the expected count.

Why we use result += [...] instead of result.extend([...])

Either works; the snippet uses += for brevity. Be careful not to mutate result while iterating over it (Python doesn't support that cleanly). The list comprehension [sub + [x] for sub in result] creates a fresh list first, then appends.

Edge cases

• Empty nums: result = [[]], the only subset.
• Duplicate elements: the algorithm treats them as distinct positions, so nums = [1, 1] gives [[], [1], [1], [1, 1]]. (The standard "Subsets II" problem requires deduplication; this version doesn't.)

Complexity

• Time: O(n · 2ⁿ) — there are 2ⁿ subsets and each takes up to O(n) to copy.
• Space: O(n · 2ⁿ) for the output. (O(1) extra working space.)

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int x : nums) {
            int size = result.size();
            for (int i = 0; i < size; i++) {
                List<Integer> sub = new ArrayList<>(result.get(i));
                sub.add(x);
                result.add(sub);
            }
        }
        return result;
    }
}

At every index, we face a binary decision: include nums[i] or skip it. That naturally forms a recursion tree of depth n with 2ⁿ leaves — each leaf is one subset.

Approach

1. Keep a running path.
2. At index i, snapshot path into result (every prefix of decisions is a valid subset).
3. Recurse on each j > i by appending nums[j] to path, then pop.