Backend interview prep

Start

Subsets (LeetCode

Learn how to solve the Subsets problem using recursion, backtracking, iterative expansion, and bit masking. Includes intuition, decision trees, Java code, dry runs, complexity analysis, duplicate handling, interview tips, and production applications.

Introduction

Subsets is one of the most important introductory backtracking problems.

It is frequently asked by companies such as:

  • Amazon
  • Google
  • Microsoft
  • Meta
  • Apple
  • Adobe
  • Bloomberg
  • Goldman Sachs
  • JPMorgan Chase

This problem teaches the fundamental backtracking pattern:

graph TD
    Choose["Choose"] --> Explore["Explore"]
    Explore["Explore"] --> Unchoose["Unchoose"]

It also introduces the idea of a decision tree, where every element creates two possibilities:

  • Include the element.
  • Exclude the element.

Once you understand Subsets, it becomes much easier to solve:

  • Permutations
  • Combinations
  • Combination Sum
  • Palindrome Partitioning
  • N-Queens
  • Sudoku
  • Word Search

Problem Statement

Given an integer array nums containing unique elements, return all possible subsets.

The solution must not contain duplicate subsets.

The subsets may be returned 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]
]

What Is a Subset?

A subset is a selection of zero or more elements from a set.

For:

[1,2]

the subsets are:

[]

[1]

[2]

[1,2]

The empty subset is always included.

What Is a Power Set?

The collection of all possible subsets is called the power set.

For n unique elements, the number of subsets is:

2^n

Why?

Each element has two choices:

Include

or

Exclude

For n elements:

2 × 2 × 2 × ... × 2

=

2^n

Decision Tree Intuition

For:

nums = [1,2,3]

At every index, make one of two decisions.

graph TD
    include_0_0["include"] --> N_1_1_1["1"]
    N_1_1_1["1"] --> include_2_1["include"]
    N_1_1_1["1"] --> N_2_2_2["2"]
    include_2_1["include"] --> N_1_3_1["1"]
    include_2_1["include"] --> N_2_3_2["2"]
    N_2_2_2["2"] --> N_1_3_3["1"]
    N_2_2_2["2"] --> N_2_3_4["2"]
    N_1_3_1["1"] --> N_3_4_1["3"]
    N_1_3_1["1"] --> N_3_4_2["-3"]
    N_2_3_2["2"] --> N_3_4_3["3"]
    N_2_3_2["2"] --> N_3_4_4["-3"]
    N_1_3_3["1"] --> N_3_4_5["3"]
    N_1_3_3["1"] --> N_3_4_6["-3"]
    N_2_3_4["2"] --> N_3_4_7["3"]
    N_2_3_4["2"] --> N_3_4_8["-3"]

Every leaf represents one subset.

Backtracking Template

A general backtracking algorithm follows this structure:

void backtrack(State state) {

    if (baseCondition) {

        saveResult();

        return;

    }

    for (Choice choice : choices) {

        choose(choice);

        backtrack(updatedState);

        unchoose(choice);

    }

}

For the Subsets problem:

State

Current subset

Choice

Include the next element

Unchoose

Remove the last element

Approach 1 — Include or Exclude Recursion

Core Idea

For each element, create two recursive branches:

  1. Include the element.
  2. Exclude the element.

This directly mirrors the binary decision tree.

Recursive Flow

graph TD
    Index["Index"] --> Include_Current_Element["Include Current Element"]
    Include_Current_Element["Include Current Element"] --> Recurse["Recurse"]
    Recurse["Recurse"] --> Remove_Current_Element["Remove Current Element"]
    Remove_Current_Element["Remove Current Element"] --> Exclude_Current_Element["Exclude Current Element"]
    Exclude_Current_Element["Exclude Current Element"] --> Recurse["Recurse"]

Java Code — Include or Exclude

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

public class SubsetsIncludeExclude {

    public List<List<Integer>> subsets(
            int[] nums) {

        List<List<Integer>> result =
                new ArrayList<>();

        backtrack(
                nums,
                0,
                new ArrayList<>(),
                result);

        return result;

    }

    private void backtrack(
            int[] nums,
            int index,
            List<Integer> current,
            List<List<Integer>> result) {

        if (index == nums.length) {

            result.add(
                    new ArrayList<>(current));

            return;

        }

        current.add(nums[index]);

        backtrack(
                nums,
                index + 1,
                current,
                result);

        current.remove(current.size() - 1);

        backtrack(
                nums,
                index + 1,
                current,
                result);

    }

}

Dry Run — Include or Exclude

Input:

[1,2]

Start:

index = 0

current = []

Include 1

current = [1]

Move to index 1.

Include 2

current = [1,2]

Reached the end.

Save:

[1,2]

Backtrack:

current = [1]

Exclude 2

Reached the end.

Save:

[1]

Backtrack:

current = []

Exclude 1

Move to index 1.

Include 2

current = [2]

Save:

[2]

Backtrack:

current = []

Exclude 2

Save:

[]

Final result:

[
  [1,2],
  [1],
  [2],
  []
]

Why Copy the Current List?

This is essential:

result.add(
        new ArrayList<>(current));

Incorrect:

result.add(current);

Why?

Because current is mutable.

The same list object is reused throughout recursion.

If the same reference is stored repeatedly, every result may end up showing the final state of that list.

Approach 2 — Standard For-Loop Backtracking

Core Idea

Add the current subset to the result immediately.

Then try adding every remaining element.

This is the most common interview implementation.

Flow

graph TD
    Save_Current_Subset["Save Current Subset"] --> Loop_from_Start_Index["Loop from Start Index"]
    Loop_from_Start_Index["Loop from Start Index"] --> Choose_Element["Choose Element"]
    Choose_Element["Choose Element"] --> Recurse_from_Next_Index["Recurse from Next Index"]
    Recurse_from_Next_Index["Recurse from Next Index"] --> Remove_Element["Remove Element"]

Java Code — Standard Backtracking

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

public class Subsets {

    public List<List<Integer>> subsets(
            int[] nums) {

        List<List<Integer>> result =
                new ArrayList<>();

        backtrack(
                nums,
                0,
                new ArrayList<>(),
                result);

        return result;

    }

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

        result.add(
                new ArrayList<>(current));

        for (int i = start;
             i < nums.length;
             i++) {

            current.add(nums[i]);

            backtrack(
                    nums,
                    i + 1,
                    current,
                    result);

            current.remove(
                    current.size() - 1);

        }

    }

}

Dry Run — Standard Backtracking

Input:

[1,2,3]

Start:

current = []

Save:

[]

Choose 1

current = [1]

Save:

[1]

Choose 2

current = [1,2]

Save:

[1,2]

Choose 3

current = [1,2,3]

Save:

[1,2,3]

Backtrack:

current = [1,2]

No more choices.

Backtrack:

current = [1]

Choose 3

current = [1,3]

Save:

[1,3]

Backtrack:

current = [1]

Backtrack:

current = []

Choose 2

current = [2]

Save:

[2]

Choose 3

current = [2,3]

Save:

[2,3]

Choose 3

current = [3]

Save:

[3]

Final result:

[
  [],
  [1],
  [1,2],
  [1,2,3],
  [1,3],
  [2],
  [2,3],
  [3]
]

Why Use i + 1?

After choosing nums[i], recurse using:

i + 1

This ensures:

  • Elements are not reused.
  • The same subset is not generated in a different order.
  • [1,2] is generated, but [2,1] is not.

Subsets do not care about ordering.

Backtracking State Changes

For every choice:

current.add(nums[i]);

This is the choose step.

Then:

backtrack(...);

This is the explore step.

Finally:

current.remove(current.size() - 1);

This is the unchoose step.

Without the removal, later recursive branches would contain values selected by earlier branches.

Complexity Analysis

For n elements, there are:

2^n

subsets.

Copying each subset may require up to:

O(n)

time.

Therefore:

Complexity Value
Time O(n × 2^n)
Output Space O(n × 2^n)
Recursion Stack O(n)

The output itself is exponential, so no algorithm can produce all subsets in polynomial total time.

Approach 3 — Iterative Expansion

Core Idea

Start with the empty subset.

For each number:

  1. Copy every existing subset.
  2. Add the current number to the copy.
  3. Add the new subset to the result.

Example

Input:

[1,2,3]

Start:

[[]]

Process 1:

[[], [1]]

Process 2:

[
  [],
  [1],
  [2],
  [1,2]
]

Process 3:

[
  [],
  [1],
  [2],
  [1,2],
  [3],
  [1,3],
  [2,3],
  [1,2,3]
]

Java Code — Iterative

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

public class SubsetsIterative {

    public List<List<Integer>> subsets(
            int[] nums) {

        List<List<Integer>> result =
                new ArrayList<>();

        result.add(new ArrayList<>());

        for (int number : nums) {

            int existingSize =
                    result.size();

            for (int i = 0;
                 i < existingSize;
                 i++) {

                List<Integer> subset =
                        new ArrayList<>(
                                result.get(i));

                subset.add(number);

                result.add(subset);

            }

        }

        return result;

    }

}

Why Capture existingSize?

This is necessary:

int existingSize = result.size();

During the loop, new subsets are added to result.

If the loop uses the continuously growing size, it may repeatedly process newly added subsets and produce incorrect results.

Iterative Complexity

Complexity Value
Time O(n × 2^n)
Space O(n × 2^n)

This approach avoids recursion but still creates the complete power set.

Approach 4 — Bit Masking

Core Idea

Every subset can be represented using an n-bit number.

For:

nums = [1,2,3]

Each bit indicates whether an element is included.

Mask Binary 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]

Java Code — Bit Masking

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

public class SubsetsUsingBitMask {

    public List<List<Integer>> subsets(
            int[] nums) {

        List<List<Integer>> result =
                new ArrayList<>();

        int subsetCount =
                1 << nums.length;

        for (int mask = 0;
             mask < subsetCount;
             mask++) {

            List<Integer> subset =
                    new ArrayList<>();

            for (int index = 0;
                 index < nums.length;
                 index++) {

                int bit =
                        1 << index;

                if ((mask & bit) != 0) {

                    subset.add(
                            nums[index]);

                }

            }

            result.add(subset);

        }

        return result;

    }

}

Bit Masking Complexity

Complexity Value
Time O(n × 2^n)
Space O(n × 2^n)

Bit masking is concise and avoids recursion, but backtracking is usually preferred because it generalizes better to more advanced constraint problems.

Comparison of Approaches

Approach Time Extra Stack Best Use
Include/Exclude Recursion O(n × 2^n) O(n) Understand binary decisions
For-Loop Backtracking O(n × 2^n) O(n) Best interview solution
Iterative Expansion O(n × 2^n) O(1) recursion Simple non-recursive option
Bit Masking O(n × 2^n) O(1) recursion Small n, bit manipulation

All approaches must generate 2^n subsets.

Handling Duplicate Input Values

LeetCode #78 assumes all input values are unique.

A common follow-up allows duplicates.

Example:

nums = [1,2,2]

Naive backtracking may generate duplicate subsets.

Expected unique subsets:

[
  [],
  [1],
  [2],
  [1,2],
  [2,2],
  [1,2,2]
]

This becomes LeetCode #90 — Subsets II.

Subsets II Strategy

  1. Sort the array.
  2. Skip duplicate values at the same recursion level.

Condition:

if (i > start
        && nums[i] == nums[i - 1]) {

    continue;

}

Java Code — Subsets with Duplicates

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

public class SubsetsWithDuplicates {

    public List<List<Integer>> subsetsWithDup(
            int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> result =
                new ArrayList<>();

        backtrack(
                nums,
                0,
                new ArrayList<>(),
                result);

        return result;

    }

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

        result.add(
                new ArrayList<>(current));

        for (int i = start;
             i < nums.length;
             i++) {

            if (i > start
                    && nums[i] == nums[i - 1]) {

                continue;

            }

            current.add(nums[i]);

            backtrack(
                    nums,
                    i + 1,
                    current,
                    result);

            current.remove(
                    current.size() - 1);

        }

    }

}

Why Skip Duplicates Only at the Same Level?

For:

[1,2,2]

The two 2 values can both appear in the same subset:

[2,2]

Therefore, duplicates cannot be skipped everywhere.

This condition:

i > start

means:

Skip an equal value only when another equal value has already been considered as a choice at the current recursion level.

Edge Cases

Empty Array

Input

[]

Output:

[
  []
]

The empty set has one subset: itself.

Single Element

Input

[5]

Output:

[
  [],
  [5]
]

Negative Values

Input

[-1,2]

Output:

[
  [],
  [-1],
  [2],
  [-1,2]
]

Multiple Elements

Input

[1,2,3,4]

Number of subsets:

2^4 = 16

Common Interview Mistakes

Mistake 1 — Forgetting to Copy the Current List

Incorrect:

result.add(current);

Correct:

result.add(
        new ArrayList<>(current));

Mistake 2 — Forgetting to Backtrack

Incorrect:

current.add(nums[i]);

backtrack(...);

Missing:

current.remove(current.size() - 1);

Without state restoration, values leak into other branches.

Mistake 3 — Recursing with start + 1

Inside the loop, use:

i + 1

not:

start + 1

The next recursion must begin after the element actually selected.

Mistake 4 — Reusing Elements

For Subsets, each input position may be used at most once in a subset.

Recursing with i instead of i + 1 may reuse the same element.

Mistake 5 — Forgetting the Empty Subset

The empty subset must always be included.

In the standard backtracking solution, it is added during the initial call.

Mistake 6 — Claiming O(2^n) Without Accounting for Copies

There are 2^n subsets, but copying each subset may take up to O(n).

The complete output-generation complexity is:

O(n × 2^n)

Mistake 7 — Using a Set to Remove Duplicate Subsets

A Set<List<Integer>> may work but adds unnecessary hashing overhead.

For duplicate input, sorting and pruning duplicate branches is cleaner and more efficient.

Production Applications

Subset generation appears in:

  • Feature-selection systems
  • Test-case generation
  • Permission combinations
  • Product-bundle generation
  • Configuration exploration
  • Rule-engine evaluation
  • Portfolio combination analysis
  • Deployment-option analysis
  • Recommendation systems
  • Access-control modeling

Real-World Example — Feature Flags

Suppose an application has three optional features:

Logging

Caching

Compression

Possible configurations include:

[]

[Logging]

[Caching]

[Compression]

[Logging, Caching]

[Logging, Compression]

[Caching, Compression]

[Logging, Caching, Compression]

This is exactly the power set of the available features.

Real-World Example — Test Configuration Generation

Suppose a system supports optional behaviors:

Authentication

Retry

Caching

Audit

A testing framework may generate all feature combinations to verify that configurations do not conflict.

For four optional settings:

2^4 = 16

test configurations exist.

In production systems, pruning may be necessary because some combinations may be invalid or too expensive to test.

Follow-Up Question 1 — Generate Only Subsets of Size k

Stop and save only when:

current.size() == k

This becomes a combinations problem.

public List<List<Integer>> subsetsOfSizeK(
        int[] nums,
        int k) {

    List<List<Integer>> result =
            new ArrayList<>();

    backtrack(
            nums,
            0,
            k,
            new ArrayList<>(),
            result);

    return result;

}

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

    if (current.size() == k) {

        result.add(
                new ArrayList<>(current));

        return;

    }

    for (int i = start;
         i < nums.length;
         i++) {

        current.add(nums[i]);

        backtrack(
                nums,
                i + 1,
                k,
                current,
                result);

        current.remove(
                current.size() - 1);

    }

}

Follow-Up Question 2 — Generate Subsets with a Target Sum

Track the running sum.

Save the subset when the sum matches the target.

Prune when possible if:

  • Values are non-negative.
  • The current sum already exceeds the target.

This idea leads toward Combination Sum problems.

Follow-Up Question 3 — Count Subsets Without Generating Them

For n unique elements:

2^n

For subsets of exactly size k:

C(n,k)

Counting is much cheaper than materializing every subset.

Follow-Up Question 4 — Process Subsets Lazily

Instead of storing every subset, pass each generated subset to a consumer.

Example:

Consumer<List<Integer>>

This can reduce retained memory when subsets can be processed one at a time.

However, the total computation remains exponential.

Follow-Up Question 5 — Can Subsets Be Parallelized?

Independent branches of the decision tree can be processed in parallel.

For example:

  • Include the first element.
  • Exclude the first element.

These branches are independent.

However:

  • Result merging is required.
  • Thread overhead can exceed the benefit for small inputs.
  • The output size remains exponential.
  • Shared mutable state must be avoided.

Follow-Up Question 6 — What If n Is Very Large?

Since the number of subsets is:

2^n

generation becomes infeasible quickly.

Examples:

n Number of Subsets
10 1,024
20 1,048,576
30 1,073,741,824
40 More than one trillion

For large n, consider:

  • Counting instead of generating
  • Pruning invalid subsets
  • Generating only subsets of a fixed size
  • Lazy iteration
  • Sampling
  • Dynamic programming for aggregate questions

Backtracking vs Brute Force

Backtracking is a structured form of exhaustive search.

It improves brute force by:

  • Building solutions incrementally
  • Reusing mutable state
  • Undoing choices
  • Pruning invalid branches early

For basic Subsets, every branch is valid, so little pruning is possible.

In more advanced problems, pruning is the main performance advantage.

Backtracking vs Dynamic Programming

Backtracking Dynamic Programming
Explores candidate solutions Reuses overlapping subproblems
Often generates all valid answers Often calculates a value or count
Uses choose/explore/unchoose Uses recurrence and memoization
Good for combinations and constraints Good for optimization and counting

Subsets generation requires producing all answers, so backtracking is a natural fit.

Interview Explanation

A strong interview explanation could be:

Each element has two possibilities: it can be included or excluded, which creates a binary decision tree with 2^n leaves. I use backtracking to maintain the current subset. At every recursion level, I add a remaining element, recurse from the next index, and then remove the element to restore the previous state. I copy the current subset into the result at every node. The total time is O(n × 2^n) because there are 2^n subsets and each subset may require O(n) time to copy.

Interview Tips

Interviewers commonly ask:

  • Why are there 2^n subsets?
  • Why is the empty subset included?
  • Why do you copy the current list?
  • Why is backtracking required?
  • What does choose–explore–unchoose mean?
  • Why recurse with i + 1?
  • How do you handle duplicate input values?
  • What is the recursion depth?
  • Can the solution be iterative?
  • Can bit masking solve the problem?
  • How would you generate only size-k subsets?
  • Can the subsets be generated lazily?
  • Why is the time complexity O(n × 2^n)?

Explain the decision tree before writing code.

Unit Tests

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.List;

import org.junit.jupiter.api.Test;

class SubsetsTest {

    private final Subsets solution =
            new Subsets();

    @Test
    void shouldGenerateAllSubsets() {

        List<List<Integer>> result =
                solution.subsets(
                        new int[]{1, 2, 3});

        assertEquals(
                8,
                result.size());

        assertTrue(
                result.contains(List.of()));

        assertTrue(
                result.contains(
                        List.of(1, 2, 3)));

        assertTrue(
                result.contains(
                        List.of(1, 3)));

    }

    @Test
    void shouldHandleSingleElement() {

        List<List<Integer>> result =
                solution.subsets(
                        new int[]{5});

        assertEquals(
                2,
                result.size());

        assertTrue(
                result.contains(List.of()));

        assertTrue(
                result.contains(
                        List.of(5)));

    }

    @Test
    void shouldHandleEmptyArray() {

        List<List<Integer>> result =
                solution.subsets(
                        new int[]{});

        assertEquals(
                1,
                result.size());

        assertEquals(
                List.of(),
                result.get(0));

    }

    @Test
    void shouldHandleNegativeValues() {

        List<List<Integer>> result =
                solution.subsets(
                        new int[]{-1, 2});

        assertEquals(
                4,
                result.size());

        assertTrue(
                result.contains(
                        List.of(-1, 2)));

    }

}

Summary

The Subsets problem is the foundation of backtracking.

Each element creates two possibilities:

Include

or

Exclude

This produces:

2^n

possible subsets.

The standard backtracking solution:

  1. Stores the current subset.
  2. Tries every remaining element.
  3. Recurses from the next index.
  4. Removes the chosen element to restore state.

Complexity:

Time: O(n × 2^n)

Recursion Stack: O(n)

Output Space: O(n × 2^n)

Key Takeaways

  • Subsets form the power set.
  • n elements produce 2^n subsets.
  • The empty subset must be included.
  • Backtracking follows choose–explore–unchoose.
  • Copy mutable state before adding it to results.
  • Recurse with i + 1 to avoid element reuse.
  • Remove the last value after recursion.
  • The for-loop backtracking approach is the preferred interview solution.
  • Iterative expansion and bit masking are valid alternatives.
  • Sort and skip same-level duplicates for Subsets II.
  • Generation is inherently exponential.
  • For large input, use pruning, counting, lazy processing, or restricted subset sizes.
  • This pattern is the foundation for combinations, permutations, and constraint-solving problems.