Problem statement

Given an array nums of distinct integers, return all possible subsets (the power set).

Output order: sort nums ascending, keep each subset in ascending order, and list subsets in DFS (prefix) order — a subset comes immediately before its extensions (e.g. [1] before [1,2], and [1,2,3] before [1,3]).

Example 1

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

Example 2

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

Constraints

• 1 <= nums.length <= 5
• -10 <= nums[i] <= 10
• All values distinct.

Hints for Subsets

1. Hint 1

   Backtracking: at each step, choose the next larger element to include, or stop.

2. Hint 2

   Push the current subset into the answer BEFORE exploring extensions to get prefix order.

How to solve Subsets

Think of building a subset by scanning the sorted values left to right and deciding how far to reach. At each step you may append any value after the last one you took. Recording the current subset the moment you arrive — before extending it — is what produces the required prefix (DFS) ordering.

Approach

1. Sort nums ascending so every subset comes out in ascending order and the enumeration is deterministic.
2. Recurse with a start index and the subset built so far.
3. First, record a copy of the current subset. Even the empty one at the root counts.
4. Then loop i from start to the end: append nums[i], recurse with i + 1, and remove it again.
5. Using i + 1 (not i) means each value is used at most once.

Why it works

Fixing a start index means every subset is generated by exactly one increasing sequence of indices, so there are no duplicates and nothing is missed — that is precisely the power set. Recording before recursing is what makes a subset appear immediately before all of its extensions, which is the DFS/prefix order the problem asks for; recording at the leaves instead would list only the maximal subsets.

Complexity

• Time — O(2^n · n)
• Space — O(2^n · n)

Pitfalls

• Push a copy of the working subset. Pushing the live array means every stored answer mutates as the search continues, and you end up with a list of identical empty arrays.
• Record before the loop, not after it, or you lose the prefix ordering.
• Undo the append after each recursive call — forgetting to backtrack leaks values into sibling branches.

Reference solution

Python

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    s = sorted(nums)
    out = []

    def go(start, cur):
        out.append(cur[:])
        for i in range(start, len(s)):
            cur.append(s[i])
            go(i + 1, cur)
            cur.pop()

    go(0, [])
    return out

Java

public static int[][] subsets(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    List<int[]> out = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    goSubsets(out, s, 0, cur);
    return out.toArray(new int[0][]);
}

private static void goSubsets(List<int[]> out, int[] s, int start, List<Integer> cur) {
    int[] snap = new int[cur.size()];
    for (int i = 0; i < cur.size(); i++) snap[i] = cur.get(i);
    out.add(snap);
    for (int i = start; i < s.length; i++) {
        cur.add(s[i]);
        goSubsets(out, s, i + 1, cur);
        cur.remove(cur.size() - 1);
    }
}

C++

void goSubsets(vector<vector<int>>& out, vector<int>& s, int start, vector<int>& cur) {
    out.push_back(cur);
    for (int i = start; i < (int) s.size(); i++) {
        cur.push_back(s[i]);
        goSubsets(out, s, i + 1, cur);
        cur.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    vector<vector<int>> out;
    vector<int> cur;
    goSubsets(out, s, 0, cur);
    return out;
}

JavaScript

var subsets = function(nums) {
    const s = nums.slice().sort(function(a, b) { return a - b; });
    const out = [];
    function go(start, cur) {
        out.push(cur.slice());
        for (let i = start; i < s.length; i++) {
            cur.push(s[i]);
            go(i + 1, cur);
            cur.pop();
        }
    }
    go(0, []);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium