71.Subsets

MediumBacktracking · 1/9

Problem

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

The answer must not contain duplicate subsets, and the subsets may be returned in any order. The empty subset [] and the full array are both valid subsets.

Examples

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Explanation: 3 elements give 2^3 = 8 subsets.

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

Constraints

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

💡 Key Insight

Every element faces exactly one binary decision: include it or skip it. With n elements that gives 2^n subsets — a full binary decision tree whose leaves are the answers. You can walk that tree with recursion (backtracking), enumerate it with the bits of a counter (bitmask), or build it level by level (cascading). All are optimal because the output itself has size n · 2^n.

Cascading (Iterative)

TimeO(n · 2^n)SpaceO(n · 2^n)

Intuition

Start with [[]]. When a new number arrives, every subset that already exists can either stay as it is or be copied with the new number appended. So processing a number doubles the list.

Algorithm

result = [[]].
For each num in nums:
- Let size = result.size().
- For each of the first size subsets, copy it, append num, and add the copy to result.
Return result.

Visualization

start            : [[]]
after num = 1    : [[], [1]]
after num = 2    : [[], [1], [2], [1,2]]
after num = 3    : [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

Code

java

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // the empty subset
        for (int num : nums) {
            int size = result.size(); // freeze the count before we start adding
            for (int i = 0; i < size; i++) {
                List<Integer> copy = new ArrayList<>(result.get(i));
                copy.add(num);
                result.add(copy);
            }
        }
        return result;
    }
}

Complexity

Time: O(n · 2^n) — 2^n subsets are created, each copy costs up to n.
Space: O(n · 2^n) — the output itself; no extra working memory beyond one copy.

Bitmask

TimeO(n · 2^n)SpaceO(n) extra besides the output.

Intuition

Number the subsets 0 .. 2^n - 1. In the binary form of a mask, bit i set means "nums[i] is in this subset". Counting from 0 to 2^n - 1 therefore visits every subset exactly once.

Algorithm

For mask from 0 to (1 << n) - 1:
- Build a list containing nums[i] for every i where (mask >> i) & 1 == 1.
- Add it to result.
Return result.

Visualization

nums = [1, 2, 3]   (bit 0 -> 1, bit 1 -> 2, bit 2 -> 3)

mask  bits  subset
0     000   []
1     001   [1]
2     010   [2]
3     011   [1,2]
4     100   [3]
5     101   [1,3]
6     110   [2,3]
7     111   [1,2,3]

Code

java

import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (((mask >> i) & 1) == 1) { // bit i chooses nums[i]
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }
}

Complexity

Time: O(n · 2^n) — 2^n masks, n bit checks each.
Space: O(n) extra besides the output.

BacktrackingOptimal

TimeO(n · 2^n)SpaceO(n)

Intuition

Walk the include/skip decision tree with depth-first search. At index i we first include nums[i], recurse, then undo that choice (remove it) and recurse again without it. When i == n, the current path is a complete subset.

Algorithm

dfs(i): if i == nums.length, add a copy of path to result and return.
Add nums[i] to path, call dfs(i + 1).
Remove the last element of path, call dfs(i + 1).
Start with dfs(0).

Visualization

flowchart TD
    R["i=0 path=[]"] -->|"take 1"| A["i=1 [1]"]
    R -->|"skip 1"| B["i=1 []"]
    A -->|"take 2"| C["i=2 [1,2]"]
    A -->|"skip 2"| D["i=2 [1]"]
    B -->|"take 2"| E["i=2 [2]"]
    B -->|"skip 2"| F["i=2 []"]
    C --> C1["[1,2,3]"]
    C --> C2["[1,2]"]
    D --> D1["[1,3]"]
    D --> D2["[1]"]
    E --> E1["[2,3]"]
    E --> E2["[2]"]
    F --> F1["[3]"]
    F --> F2["[]"]

Code

java

import java.util.*;

class Solution {
    private final List<List<Integer>> result = new ArrayList<>();
    private final List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return result;
    }

    private void dfs(int[] nums, int i) {
        if (i == nums.length) {
            result.add(new ArrayList<>(path)); // snapshot, path keeps changing
            return;
        }
        path.add(nums[i]);       // choice 1: include nums[i]
        dfs(nums, i + 1);
        path.remove(path.size() - 1); // undo
        dfs(nums, i + 1);        // choice 2: skip nums[i]
    }
}

Complexity

Time: O(n · 2^n) — 2^n leaves, each copied in O(n).
Space: O(n) — recursion depth and path (output excluded).

Complexity Comparison

Approach	Time	Space (extra)
Cascading	O(n · 2^n)	O(n)
Bitmask	O(n · 2^n)	O(n)
Backtracking	O(n · 2^n)	O(n)

Common Pitfalls

Adding path itself instead of new ArrayList<>(path) — every entry ends up pointing at the same (finally empty) list.
In the cascading approach, looping i < result.size() while adding to result — an infinite loop. Freeze size first.
Forgetting the empty subset — it is part of the power set.
Using 1 << n for large n overflows an int past 31; fine here since n <= 10.