⊂

Subsets — Include or Exclude Each Element

At each element, make two choices: include it in the current subset or skip it. Collect the current path at every node of the recursion tree — no leaf-only collection needed.

⊂ 2ⁿ Subsets 🔄 With Duplicates (Subsets II) 📋 Collect Every State Time O(2ⁿ·n) Space O(n)

📋 When to Use

Generate all 2ⁿ subsets of an array
Subsets II: sort input first, skip nums[i]==nums[i-1] when i > start to avoid duplicate subsets
Start index increments each recursion — no element reused from earlier positions
Collect new ArrayList<>(curr) at the start of each call (includes the empty set automatically)

💡 Unlike permutations, subsets pass i+1 (not 0) to avoid re-picking earlier elements. The empty set [] is added on the very first call before the loop runs.

⚡ Complexity

Time

O(2ⁿ·n)

Space (stack)

O(n)

2ⁿ subsets total; each copy is O(n).
Recursion depth = n (one element per level).
Output space: O(2ⁿ × n) to store all subsets.
n=3 → 8 subsets: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

Problem Given nums = [1,2,3], generate all possible subsets (the power set). At each element decide include or skip — with n=3 elements there are 2³ = 8 subsets total. Collect the current path at every node of the recursion tree, not just at leaves.
Input: nums = [1,2,3] · Answer: 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

Step 0 / 15

🔍 Init 📋 Add to Result ➕ Choose Element ↩ Backtrack ✅ Done

Starting the Subsets backtracking with input [1, 2, 3]. We'll collect subsets at every call, building the power set.

// backtrack(start=0, curr=[])

Recursion Tree — nums = [1, 2, 3]

Active

In Stack

Returned

Not Visited

📚 Call Stack

— empty —

Input

nums[0..2]

curr[ ]

[ ] empty

Result (subsets found)

none yet

Pattern Skeleton Java 8

// ─── Subsets (all 2ⁿ subsets) ────────────────────────────────────
List<List<Integer>> result = new ArrayList<>();
int[] nums;

void backtrack(int start, List<Integer> curr) {
    result.add(new ArrayList<>(curr));        // collect every state
    for (int i = start; i < nums.length; i++) {
        curr.add(nums[i]);                    // choose
        backtrack(i + 1, curr);              // explore (i+1: no reuse)
        curr.remove(curr.size() - 1);        // un-choose (backtrack)
    }
}
// Call: backtrack(0, new ArrayList<>())

// ─── Subsets II (with duplicates — sort first) ───────────────────
void backtrack(int start, List<Integer> curr) {
    result.add(new ArrayList<>(curr));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i-1]) continue; // skip dup
        curr.add(nums[i]);
        backtrack(i + 1, curr);
        curr.remove(curr.size() - 1);
    }
}

Practice Problems

#78 Subsets classic power set Medium #90 Subsets II with duplicates — sort + skip Medium #784 Letter Case Permutation choose uppercase or lowercase each char Medium #1239 Maximum Length of a Concatenated String with Unique Characters subset pruning with bitmask Medium