Subsets (Power Set)

Learning to Explore Every Possibility Without Missing Any

The Subsets problem tests whether you understand how to explore a decision tree without missing cases or duplicating work. It's a classic interview question because the same thinking shows up across backtracking, bit manipulation, and combinatorics problems.

Problem Statement

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

Examples:

• [1, 2, 3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

• [1, 2] → [[], [1], [2], [1,2]]

• [] → [[]]

1. Clarify Requirements Before Jumping Into Code

Before writing code, restate the rules.

Input: An array of distinct integers.

Output: A list of all possible subsets, including the empty set.

Key rules:

• Each element is either included or excluded. Elements do not twice in a single subset.

• The empty set must be included.

• No duplicate subsets in the output.

Quick checks to raise:

• If nums is empty, the answer is [[]] - one subset, the empty one.

• Elements in nums are distinct, so we don't need to worry about deduplicating subsets.

• Order of subsets in the output doesn't matter.

2. Identify the Category of the Problem

This is a backtracking problem. At each position in the array, you make a binary decision: include this element or skip it. Explore both options, then undo your choice and move on.

If you've already worked through Permutations, the structure here is familiar, but there's one important difference. In Permutations, you only record a result when you've placed every element. Here, every partial state is a valid answer. You record the current subset at every step, not just at the leaves of the recursion tree.

3. Start With Brute Force to Build Intuition

Like Permutations, there's no way to beat the output size here. With n elements, each element has two choices - in or out - so there are 2ⁿ possible subsets. Any correct solution must generate all of them.

For n = 3, that's 8. For n = 10 that's 1024. The challenge isn't speed - it's correctness and structure. How do you make sure you generate every subset exactly once without duplicating or missing any?

4. Brainstorm More Solutions

Step 1: Think About How You'd Do This By Hand

Forget code. If someone asked you to list all subsets of [1, 2, 3] on paper, how would you approach it?

One natural method: go through the elements one by one and, for each one, decide whether it's in or out. You might draw a tree:

Start: {}
  Include 1: {1}
    Include 2: {1,2}
      Include 3: {1,2,3} ✓
      Exclude 3: {1,2} ✓
    Exclude 2: {1}
      Include 3: {1,3} ✓
      Exclude 3: {1} ✓
  Exclude 1: {}
    Include 2: {2}
      Include 3: {2,3} ✓
      Exclude 3: {2} ✓
    Exclude 2: {}
      Include 3: {3} ✓
      Exclude 3: {} ✓

Every node in that tree is a valid subset. That's the key insight that makes this problem different from Permutations: you don't wait until the bottom to record results - every level of the tree is an answer.

Step 2: Translate to Recursion

This decision tree maps directly to a recursive structure. At each call, we're at some index start, and we've already decided what to do with all elements before it. We record the current subset, then loop through remaining elements - for each one, add it and recurse deeper, then remove it before trying the next.

Why do we loop from start forward and not from 0? Because subsets don't care about order. {1, 2} and {2, 1} are the same subset. By always moving forward in the array, we ensure each combination is generated exactly once. This start index is the key mechanism that prevents duplicates.

Let's trace [1, 2, 3]:

backtrack(start=0, subset=[])
  record []
  i=0: add 1 → backtrack(start=1, subset=[1])
    record [1]
    i=1: add 2 → backtrack(start=2, subset=[1,2])
      record [1,2]
      i=2: add 3 → backtrack(start=3, subset=[1,2,3])
        record [1,2,3]
        loop ends (start=3 == length)
      remove 3
    remove 2
    i=2: add 3 → backtrack(start=3, subset=[1,3])
      record [1,3]
    remove 3
  remove 1
  i=1: add 2 → backtrack(start=2, subset=[2])
    record [2]
    i=2: add 3 → backtrack(start=3, subset=[2,3])
      record [2,3]
    remove 3
  remove 2
  i=2: add 3 → backtrack(start=3, subset=[3])
    record [3]
  remove 3

Results collected in order: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]. All 8 subsets, no duplicates.

Notice the discipline: every add has a corresponding remove. The subset is always restored to exactly the state it was in before the recursive call. That's the backtracking contract.

Step 3: Is There a Non-Recursive Approach?

It's worth knowing two alternatives, even if backtracking is what you'd code in an interview.

Iterative expansion: Start with [[]]. For each number in nums, take every existing subset and create a new version with that number appended. For example, after processing 1, 2, and 3:

Start:      [[]]
After 1:    [[], [1]]
After 2:    [[], [1], [2], [1,2]]
After 3:    [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

This is clean and easy to explain, but it requires storing all intermediate subsets in memory - O(2ⁿ × n) space.

Bit masking: For n elements, there are 2ⁿ numbers from 0 to 2ⁿ - 1. Each number's binary representation tells you which elements to include: bit k set means include nums[k].

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}

This is compact and elegant, but it requires explaining binary representations under pressure, and it doesn't generalize as naturally to problems with constraints (like "subsets that sum to a target").

Backtracking is the right default: it makes the decision tree explicit, it's easy to reason about, and it adapts cleanly to harder variants.

5. Trade-Offs at a Glance

Approach	Time	Space	Notes
Backtracking	O(2ⁿ × n)	O(n)	Clear, adaptable, preferred
Iterative expansion	O(2ⁿ × n)	O(2ⁿ × n)	Simple logic; high memory
Bit masking	O(2ⁿ × n)	O(n)	Compact; harder to explain and adapt

The O(n) factor in time comes from copying each subset when we record it. Space refers to the recursion stack depth, not the output.

6. Pseudocode

result = empty list

backtrack(start, subset):
    add a copy of subset to result      ← record at every level

    for i from start to nums.length - 1:
        add nums[i] to subset           ← choose
        backtrack(i + 1, subset)        ← explore
        remove last element from subset ← un-choose

call backtrack(0, empty list)
return result

Compare this to the Permutations pseudocode. The structure is nearly identical. The two differences are: we record results at every level (not just when the path is full), and we use a start index to move forward only (not a used array).

7. Edge Cases

• Empty input: The first call records an empty subset immediately and the loop never executes. Output: [[]].

• Single element: Two subsets - [] and [the element]. Good sanity check.

• Larger inputs: For n = 3, verify you get exactly 8 subsets. Count before you check contents.

Since elements are distinct, no deduplication is needed. If the problem ever introduces duplicates (a common follow-up variant), the start index approach adapts - you'd sort the array first and skip consecutive duplicates at the same recursion level.

8. Full Solution

import java.util.ArrayList;
import java.util.List;

public class Subsets {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int start,
                                   List<Integer> subset,
                                   List<List<Integer>> result) {

        // record current subset (copy, not reference)
        result.add(new ArrayList<>(subset));  

        for (int i = start; i < nums.length; i++) {
            subset.add(nums[i]);                    // choose
            backtrack(nums, i + 1, subset, result); // explore
            subset.remove(subset.size() - 1);       // un-choose
        }
    }
}

The same warning from Permutations applies: result.add(new ArrayList<>(subset)) - always copy. If you pass the reference, every stored subset will end up pointing to the same list, which will be empty by the time recursion finishes.

9. Test Your Solution

System.out.println(subsets(new int[]{}));
// [[]]

System.out.println(subsets(new int[]{1}));
// [[], [1]]

System.out.println(subsets(new int[]{1, 2}));
// [[], [1], [1,2], [2]]

System.out.println(subsets(new int[]{1, 2, 3}));
// 8 subsets — count first, then spot-check a few

It's worth tracing the two-element case by hand against the recursion trace above. If your output order matches the trace, you have strong confidence the logic is right.

10. Key Lessons for Future Problems

• Every recursive state is a valid answer. This is what makes Subsets different from Permutations. When the problem asks for all possible intermediate states - not just the complete ones - record results at every level, not just the leaves.

• Backtracking generalizes. The choose → explore → un-choose structure here is nearly identical to Permutations. Combination Sum uses the same skeleton with a target constraint. Subsets with Duplicates adds a sort and a skip. Once you own this pattern cleanly, a whole family of problems opens up.

• Know the alternatives. Iterative expansion and bit masking both work. Being able to describe them - and explain why you'd choose backtracking anyway - shows depth. Interviewers notice when you've thought past the first correct solution.

Subsets teaches a foundational skill: exploring all possibilities systematically without chaos. Once that mindset is solid, combinatorial problems stop feeling like they require memorization and start feeling like variations on a structure you already understand.

Good Luck and Happy Coding!