Subsets

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given a list of distinct integers, return all of its subsets (the power set). Each subset is a list of some of the numbers, including the empty subset and the full list. The result must not contain the same subset twice, and subsets and their contents may be in any order.

    The entry point to backtracking. Interviewers use it to see whether you can write a clean choose / explore / undo loop and explain why it never produces duplicates. Original problem: LeetCode 78.

    Example

    For nums = [1, 2, 3] there are 8 subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3]. Each number is either in or out, so 2 × 2 × 2 = 8.
    For nums = [1, 2, 3] there are 8 subsets: [], [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3]. Each number is either in or out, so 2 × 2 × 2 = 8.
    Input:  nums = [1, 2, 3]
    Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]   # any order
    Input:  nums = [0]
    Output: [[], [0]]

    Constraints (assumed)

    • 1 ≤ n ≤ 10.
    • −10 ≤ nums[i] ≤ 10, all distinct.

    What this question tests

    • Writing the backtracking template (choose, explore, undo) without bugs.
    • Avoiding duplicate subsets by only moving forward through the list.
    • Knowing the output size (2ⁿ) and why no algorithm can beat O(n · 2ⁿ).

    Questions to ask first

    1. Are the numbers distinct? (Yes. With duplicates, see Subsets II below.)
    2. Does the order of subsets, or of numbers inside a subset, matter? (No.)
    3. Should the empty subset be included? (Yes.)
    4. How large can n be? The output doubles with each number, so n is always small; n = 30 would already be a billion subsets.