DSA-118 · Backtracking with independent path snapshots

Subsets

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 17 deterministic checks. Learner drafts are not executed.

Understand the problem

Return every subset of an array of distinct integers, including the empty subset. Each subset uses elements at most once and preserves their input-relative order.

nums is non-null with 0–16 distinct signed int values. Duplicate input values are outside this contract.
Return every subset exactly once. The outer result order is unrestricted; elements inside each subset retain input order. Empty input returns a list containing one empty list.
Preserve nums. Every returned inner list must be independent of every other list and the working path. This is full materialization, not a lazy iterator.

Examples

Input: [1,2]
Output: [[],[1],[1,2],[2]]
All four choices appear; another outer order is also valid.
Input: []
Output: [[]]
The empty set has one subset, itself.

Before you start

Power sets and output-sensitive complexity
Mutable list aliasing and undo operations

Recognize the structure

The output asks for all combinations rather than one optimum. A choice path must be explored completely and then undone. No algorithm can materialize exponentially many subsets in polynomial total output time.

Try before revealing

Hint 1

Describe a subset as an increasing sequence of chosen input indices.

Hint 2

Each recursive state already represents one valid subset.

Hint 3

Copy the path, choose a later index, recurse after it, then undo.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate bit masks

For n values, inspect masks from 0 to 2^n-1. Bit i chooses nums[i]; append selected values in increasing index order. On [1,2], masks 00,01,10,11 produce [],[1],[2],[1,2]. Checking n bits for every mask costs O(n2^n). The n≤16 bound makes 1<<n safe; this would need review for larger n.

Improve the baseline

Interpret each path as a subset

At recursive entry, copy the current path into the result. The empty initial path emits the empty subset.

Choose only later indices

From start, try each i≥start, append nums[i], and recurse with i+1. Increasing chosen indices prevent repeated elements and permutations of the same subset.

Undo before the next sibling

Remove the last path element after recursion. Copying the path when emitting prevents later undo operations from changing stored subsets. Backtracking changes enumeration structure, not the exponential output lower bound.

Why it is correct

Initialize

The initial empty path is a valid subset whose next eligible index is 0.

Preserve and avoid duplicates

Each path contains strictly increasing input indices. Choosing index i extends it validly, and i+1 prevents reuse. Every nonempty subset has a unique increasing index sequence, hence one recursion path.

Cover and finish

Every possible increasing choice sequence is explored by the for loop, and each entry emits its path. Depth is at most n and each loop is finite. Thus every subset, including empty, appears exactly once.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

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

public final class Solution {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        extend(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private static void extend(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            extend(nums, i + 1, path, result);
            path.removeLast();
        }
    }

    public static List<List<Integer>> baseline(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << nums.length); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) subset.add(nums[i]);
            result.add(subset);
        }
        return result;
    }
}

Read the meaningful blocks

Snapshot the path

new ArrayList<>(path) copies current content; adding path directly would alias all results.

Advance the index frontier

i+1, not start+1 or i, expresses that chosen indices strictly increase.

Undo exactly one choice

removeLast restores the parent’s path before trying the next candidate.

Complexity

For n≥1, materialized output contains 2^n lists and n2^(n-1) element entries; total time and output space are Θ(n2^n). Empty input has constant work/output.

Auxiliary workspace excluding output is O(n) for path and recursion. The bit-mask baseline has O(n) temporary subset space plus the same output; backtracking does not magically avoid output storage.

Exact-state walkthroughs

Reveal normal and boundary traces

Choose, recurse, undo

Input: [1,2] · Result: [[],[1],[1,2],[2]]

Step 1 of 11: Copy the current path into output.

Each emitted list is an independent snapshot of one increasing-index choice path.

Current backtracking path

Empty at this step.

State after this step
Variable	Value
start	`0`
path	`[]`
subsets	`[[]]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public final class Solution {
 5     public static List<List<Integer>> subsets(int[] nums) {
 6         List<List<Integer>> result = new ArrayList<>();
 7         extend(nums, 0, new ArrayList<>(), result);
 8         return result;
 9     }
10     private static void extend(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
11         result.add(new ArrayList<>(path));
12         for (int i = start; i < nums.length; i++) {
13             path.add(nums[i]);
14             extend(nums, i + 1, path, result);
15             path.removeLast();
16         }
17     }
18 
19     public static List<List<Integer>> baseline(int[] nums) {
20         List<List<Integer>> result = new ArrayList<>();
21         for (int mask = 0; mask < (1 << nums.length); mask++) {
22             List<Integer> subset = new ArrayList<>();
23             for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) subset.add(nums[i]);
24             result.add(subset);
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Copy the current path into output.
Each emitted list is an independent snapshot of one increasing-index choice path.
start
0
path
[]
subsets
[[]]
Choose the next index.
The chosen index is later than every ancestor choice.
start
0
i
0
path
[1]
subsets
[[]]
Copy the current path into output.
Each emitted list is an independent snapshot of one increasing-index choice path.
start
1
path
[1]
subsets
[[],[1]]
Choose the next index.
The chosen index is later than every ancestor choice.
start
1
i
1
path
[1,2]
subsets
[[],[1]]
Copy the current path into output.
Each emitted list is an independent snapshot of one increasing-index choice path.
start
2
path
[1,2]
subsets
[[],[1],[1,2]]
Undo exactly the last choice.
The parent path is restored before its next sibling.
start
1
i
1
path
[1]
subsets
[[],[1],[1,2]]
Undo exactly the last choice.
The parent path is restored before its next sibling.
start
0
i
0
path
[]
subsets
[[],[1],[1,2]]
Choose the next index.
The chosen index is later than every ancestor choice.
start
0
i
1
path
[2]
subsets
[[],[1],[1,2]]
Copy the current path into output.
Each emitted list is an independent snapshot of one increasing-index choice path.
start
2
path
[2]
subsets
[[],[1],[1,2],[2]]
Undo exactly the last choice.
The parent path is restored before its next sibling.
start
0
i
1
path
[]
subsets
[[],[1],[1,2],[2]]
Return the contract result.
The final state satisfies the requested output contract.
result
[[],[1],[1,2],[2]]

The empty subset

Input: [] · Result: [[]]

Step 1 of 2: Copy the current path into output.

Each emitted list is an independent snapshot of one increasing-index choice path.

Current backtracking path

Empty at this step.

State after this step
Variable	Value
start	`0`
path	`[]`
subsets	`[[]]`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public final class Solution {
 5     public static List<List<Integer>> subsets(int[] nums) {
 6         List<List<Integer>> result = new ArrayList<>();
 7         extend(nums, 0, new ArrayList<>(), result);
 8         return result;
 9     }
10     private static void extend(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
11         result.add(new ArrayList<>(path));
12         for (int i = start; i < nums.length; i++) {
13             path.add(nums[i]);
14             extend(nums, i + 1, path, result);
15             path.removeLast();
16         }
17     }
18 
19     public static List<List<Integer>> baseline(int[] nums) {
20         List<List<Integer>> result = new ArrayList<>();
21         for (int mask = 0; mask < (1 << nums.length); mask++) {
22             List<Integer> subset = new ArrayList<>();
23             for (int i = 0; i < nums.length; i++) if ((mask & (1 << i)) != 0) subset.add(nums[i]);
24             result.add(subset);
25         }
26         return result;
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Copy the current path into output.
Each emitted list is an independent snapshot of one increasing-index choice path.
start
0
path
[]
subsets
[[]]
Return the contract result.
The final state satisfies the requested output contract.
result
[[]]

Test the contract

Input: [7]
Output: [[],[7]]
Two choices.
Input: [0,-1]
Output: [[],[0],[0,-1],[-1]]
Values are not required to be positive or sorted.
Input: [3,1]
Output: [[],[3],[3,1],[1]]
Within-subset order follows input.
Input: [1,2,3]
Output: 8 subsets
Every input position has two inclusion choices.

Common mistakes and counterexamples

Store the working list directly

Counterexample: After undo, multiple results can all look empty.

Copy on emission.

Recurse from the chosen index again

Counterexample: [1] can be reused indefinitely.

Advance to i+1.

Omit the empty path

Counterexample: [1] must return both [] and [1].

Emit at every entry, including the root.

Claim linear total time

Counterexample: Sixteen elements already require 65,536 subsets.

Include output copying and size.

Follow-ups

Allow duplicate input values but unique value subsets.

Sort a copy and skip equal candidates at the same recursion depth. Duplicate pruning belongs to sibling choices, not all depths; preserve input if promised.

Return only subsets of size k.

Emit only at size k and prune when too few candidates remain. Output count becomes binomial(n,k), with copying cost proportional to k.

Provide a lazy iterator.

Retain enumeration state and produce one independent subset at a time. This reduces retained output memory but not total work when all subsets are eventually consumed.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 151/20,000 characters

Self-review

I copy each output path.I enforce strictly increasing chosen indices.I include empty output and exponential materialization cost.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Backtracking: choose, recurse, restore

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.