Difficulty: MediumBacktracking

Subsets

Problem in Plain English

Given an array of unique integers, return every possible subset including the empty set. The answer always holds two raised to the array length subsets.

Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets, and the subsets may be returned in any order.

Constraints

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Examples

Example 1

Input: nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Each of the three positions is either included or excluded, producing $2^3 = 8$ distinct subsets. The empty subset excludes everything, and [1, 2, 3] includes everything. The displayed order is one valid order; backtracking returns the same subsets in a different order.

Example 2

Input: nums = [0]
Output: [[], [0]]

A single element yields exactly two subsets: the empty set and the element itself.

Example 3

Input: nums = [-1, 0, 1]
Output: [[], [-1], [0], [-1, 0], [1], [-1, 1], [0, 1], [-1, 0, 1]]

Zero is an element that can be included, so [] and [0] differ. Opposite signs do not cancel elements: [-1, 1] is still a subset. Membership, rather than a sum or sign, defines each of the eight answers.

Intuition

A subset chooses which positions to keep; it does not rearrange the chosen values. Each of the n positions has two choices, so there are $2^n$ answers. For [1, 2, 3], the subsets without 3 are [], [1], [2] and [1, 2]; adding 3 to a separate copy of each produces the other four. Iterative doubling stores these choices as it goes, while backtracking keeps one temporary path and snapshots it only after all choices are settled.

Approaches

Cascading Build

Solution Details

Reveal Cascading Build: intuition, complexity, and code

Intuition

Start from a list holding only the empty subset and fold each number in by cloning every subset found so far with the new number appended. Each number doubles the result, so after the last number every combination has been built exactly once.

Step-by-Step Logic

Initialize the result with the empty subset. Generally, before processing a value, it contains every subset of the earlier prefix; Example 1 starts with [[]].
Freeze the current result size before appending anything. For each of those original subsets, allocate a copy and append the next value; new subsets must not be revisited in the same round.
With 1, copy [] to [1]. With 2, the frozen size is two, so copy [] and [1] to [2] and [1, 2].
With 3, the frozen size is four: append [3], [1, 3], [2, 3] and [1, 2, 3] in that order.
After every input value has been processed, return the result. Example 1 returns eight independent lists, including the empty and full subsets.

Why It Works

Initially the result contains exactly the subsets of the empty prefix: just the empty subset. Assume it contains each subset of the processed prefix exactly once. For the next unique value, keep every old subset as the exclude choice and append that value to a new copy of every old subset as the include choice. These two groups are disjoint because only the second contains the new value. Every subset of the enlarged prefix belongs to exactly one group, so induction proves completeness and uniqueness after the final value.

Dry Run

Cascading Build: variable states at each step
Value	Frozen size	i	Source subset	New independent subset	Result size after
start	-	-	-	`[]`	1
1	1	0	`[]`	`[1]`	2
2	2	0	`[]`	`[2]`	3
2	2	1	`[1]`	`[1, 2]`	4
3	4	0	`[]`	`[3]`	5
3	4	1	`[1]`	`[1, 3]`	6
3	4	2	`[2]`	`[2, 3]`	7
3	4	3	`[1, 2]`	`[1, 2, 3]`	8
return	-	-	-	`[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]`	8

Complexity Analysis

Time Complexity

O(n \cdot 2^n)

Space Complexity

O(n \cdot 2^n)

Let n be the input length. There are $2^n$ output lists and $n \cdot 2^{n-1}$ stored element occurrences, because each value occurs in half the subsets. Copying and appending accounts for $O(n \cdot 2^n)$ time and total output storage. Beyond the returned lists, the iteration holds only a constant number of references and counters: $O(1)$ auxiliary space. Every newly allocated list becomes part of the result; the input is not modified.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class Solution {5    public List<List<Integer>> subsets(int[] nums) {6        List<List<Integer>> result = new ArrayList<>();7        result.add(new ArrayList<>());8        for (int num : nums) {9            // Freeze the old frontier: new subsets already contain num.10            int size = result.size();11            for (int i = 0; i < size; i++) {12                // Copy so the exclude subset remains independent.13                List<Integer> next = new ArrayList<>(result.get(i));14                next.add(num);15                result.add(next);16            }17        }18        return result;19    }20}

Hints

Hint 1

Draw the decision tree for [1, 2, 3]: at each element you either take it or skip it, and each root-to-leaf path is one subset.

Hint 2

Let a recursive call own one index plus the shared current path, and record a copy of current when the index runs past the end.

Hint 3

After the take-branch returns, remove the element you just appended before running the skip-branch, or every later subset keeps it.

Edge Cases

A single-element array must yield exactly two subsets, [] and the element itself.
With n = 10 the answer holds 1024 subsets, which fits easily but confirms the doubling pattern.
Negative numbers and zero need no special casing since only positions, never values, drive the choices.
Unsorted input still works and preserves input order within each subset; sorting is unnecessary.
Although an empty input would naturally return [[]], the published constraints require at least one element.

Common Mistakes and Interview Tips

Pushing the live current reference into the answer instead of a copy, so every stored subset mutates together.
Forgetting to pop after the take-branch, which leaks the element into the skip-branch subsets.
Assuming the output order matters and adding a sort or dedup pass the problem never asks for.
Using the growing result size as the cascading loop boundary processes newly appended subsets again; capture the size before the round.
Treating zero as an absent element or comparing subsets by their sums merges different valid answers.
Interview tip: distinguish auxiliary space from output storage. Any explicit answer contains exponentially many lists, even when the working path is linear.

Key Takeaway

Binary take-or-skip backtracking enumerates every subset exactly once, and the same include-exclude skeleton extends to combinations and partitions with extra pruning.