Free lesson · DSA Mastery - Interview Prep, End to End

Subsets

Medium7 min readdsarecursion-backtracking

Subsets

Subsets is where backtracking truly begins - and it's the purest backtracking problem there is. The task: generate every subset of a set of distinct integers. This is the decision tree from the introduction made literal: at each element you make a binary choice, include it or exclude it, and the 2^n leaves of that tree are exactly the 2^n subsets. Mastering this problem establishes the choose / recurse / undo template that every remaining problem in this section builds upon. We present two equivalent backtracking formulations - the include/exclude binary tree and the "start index" iteration - because recognizing they're the same idea in two shapes is what unlocks the combination problems that follow.

The insight: a subset is a sequence of independent yes/no decisions, one per element. Backtracking walks all 2^n decision paths, recording the current partial subset at every node (not just the leaves), because in this problem every node of the tree is a valid subset.

The Problem

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.

Example 1:

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

Example 2:

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

Constraints:

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

Approaches Overview

Both generate all 2^n subsets and cost O(n · 2^n) (there are 2^n subsets, each up to length n to copy). The include/exclude form shows the binary decision tree explicitly; the start-index form generalizes directly to combinations, so it's worth learning both.

Approach 1: Backtracking (Include / Exclude) - Canonical

The Idea

Process elements one at a time by index i. At each element, branch twice: exclude nums[i] (recurse to i+1 without adding it) and include nums[i] (add it, recurse to i+1, then remove it - the backtrack). When i reaches the end, the current path is a complete subset; record it. Every one of the 2^n root-to-leaf paths produces a distinct subset.

Logic Flowchart

graph TD
    A["backtrack(i, path)"] --> B{"i == n?"}
    B -->|Yes| C["record copy of path"]
    B -->|No| D["EXCLUDE: backtrack(i+1, path)"]
    D --> E["INCLUDE: path.add(nums[i])"]
    E --> F["backtrack(i+1, path)"]
    F --> G["path.remove(last) - undo"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This flowchart shows the include-exclude backtracking. At each element we first recurse without it, then add it, recurse with it, and remove it to undo. When the index reaches the end, the current path is recorded as a complete subset.

Code

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 i, List<Integer> path, List<List<Integer>> result) {
    if (i == nums.length) {
        result.add(new ArrayList<>(path));   // complete subset: snapshot it
        return;
    }
    backtrack(nums, i + 1, path, result);     // EXCLUDE nums[i]
    path.add(nums[i]);                        // INCLUDE nums[i]
    backtrack(nums, i + 1, path, result);
    path.remove(path.size() - 1);             // UNDO - restore for the sibling branch
}

// Usage:
// subsets([1,2,3]) -> [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] (any order)

This Java code generates subsets by branching at each element: recurse excluding it, then add it, recurse including it, and remove it to restore state. At the end of the array the current path is snapshotted into the result.

Complexity

Time: O(n · 2^n) - 2^n subsets, each copied in up to O(n). Space: O(n) recursion depth (output excluded).

Approach 2: Backtracking (Start Index) - Cleaner for Combinations

The Idea

A different but equivalent framing: every node is a subset, so record path at the start of every call (not only at leaves). Then loop j from a start index to the end, and for each j, include nums[j] and recurse with start = j + 1 (so each element is considered once, in increasing index order, preventing duplicates). This "pick the next element from those after start" structure is exactly what combinations need.

Logic Flowchart

graph TD
    A["backtrack(start, path)"] --> B["record copy of path (every node is a subset)"]
    B --> C["for j = start .. n-1"]
    C --> D["path.add(nums[j])"]
    D --> E["backtrack(j+1, path)"]
    E --> F["path.remove(last) - undo"]
    F --> G{"more j?"}
    G -->|Yes| C
    G -->|No| H["return"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the start-index backtracking. Every node records the current path as a subset. A loop picks each later element in turn, adds it, recurses from the next index, then removes it. Considering elements only after the start index prevents duplicate subsets.

Code

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

private static void backtrackStart(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));        // every node is a valid subset
    for (int j = start; j < nums.length; j++) {
        path.add(nums[j]);                    // choose nums[j]
        backtrackStart(nums, j + 1, path, result);  // recurse on elements after j
        path.remove(path.size() - 1);         // undo
    }
}

This Java code records the current path at every node, then loops over each element from the start index onward, adding it, recursing from the next index, and removing it. Restricting to elements after the start index avoids duplicates.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [1,2,3] using the start-index form:

graph LR
    F0["start0 record [] ; pick 1"]
    F1["start1 record [1]; pick 2 → record [1,2]; pick 3 → [1,2,3]"]
    F2["back to [1]; pick 3 → record [1,3]"]
    F3["back to []; pick 2 → [2],[2,3]; pick 3 → [3]"]
    F4["all 8 subsets recorded"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough generates subsets of one, two, three. Starting from the empty set, it picks each element in increasing order and recurses on later elements, recording the empty set, one, one-two, one-two-three, one-three, two, two-three, and three.

Result: all 8 subsets of [1,2,3].

Complexity

Time: O(n · 2^n). Space: O(n) recursion depth.

Complexity Comparison

Both are optimal - the output alone is size 2^n, so you cannot beat O(2^n). The include/exclude form is the clearest illustration of the binary decision tree; the start-index form is the one to internalize, because Combinations, Combination Sum, and their variants are all "start index" backtracking with an added constraint.

Variations & Follow-ups

Why record at every node in the start-index version but only at leaves in include/exclude?

They count subsets differently. In include/exclude, a subset is fully determined only after deciding every element, so the complete subset exists only at a leaf. In the start-index form, each node already represents a finished subset (the elements chosen so far), and the loop extends it - so each node is recorded. Both enumerate the same 2^n subsets.

Why does start = j + 1 prevent duplicates?

By only ever picking elements with index greater than the last picked, every subset is generated in strictly increasing index order - a canonical form. [1,3] is produced (pick 1, then 3) but [3,1] never is, because once you pick index 2 you can't go back to index 0. One canonical ordering per subset means no duplicates.

How do I adapt this to "subsets of size k" (i.e., combinations)?

Add a base case: when path.size() == k, record and return (don't extend further). That's literally the Combinations problem (19.10) - the start-index template plus a size target. The connection is why this form is worth mastering.

What about the iterative "cascading" approach?

You can build subsets without recursion: start with [[]], and for each number, append it to copies of every existing subset. This doubles the list per element, reaching 2^n. It's elegant and O(n · 2^n) too, but the backtracking template is what generalizes to the constrained problems ahead, so it's the focus here.

What about edge cases?

• Single element (Example 2): Produces [] and [0].
• Empty input: Would yield just [[]] (only the empty subset) - though constraints guarantee n ≥ 1.
• Order of output: Any order is accepted; the two approaches emit subsets in different orders, both valid.
• Negative numbers: Treated as ordinary distinct elements; no special handling.

Common Interview Pitfalls

• Forgetting to snapshot path. You must add new ArrayList<>(path); adding path itself stores a reference that later mutations corrupt.
• Missing the undo. Without path.remove(...), sibling branches inherit stale elements.
• Re-scanning from index 0. Looping from 0 instead of start generates permutations and duplicate subsets.
• Recording only at leaves in the start-index form. Every node is a subset there; recording only at the end loses most of them.

Why This Topic Matters

Subsets is the foundational backtracking problem - the decision tree, the choose/recurse/undo rhythm, and the snapshot-the-path discipline all appear here in their simplest form. The start-index template you learn here is, with small additions, the entire engine for combinations and combination-sum problems. Get this one in your fingers and half of this section is already solved.

The next topic, Combination Sum, adds the first real constraint and pruning to the template: find all combinations of candidates (reusable) that sum to a target. You keep the start-index structure but allow re-picking the same element, prune branches whose running sum exceeds the target, and stop when you hit it exactly. It's the first problem where a constraint actively shapes - and prunes - the search tree.

Back to DSA Mastery - Interview Prep, End to End