Subsets

mediumBacktracking56 stepsJava · Python · C++

Generate every subset. At each recursion level, record the current path as a subset, then try extending it with each remaining element after start. Undo the choice after recursing. Using only later elements avoids duplicates like [2, 1].

▶ Watch the animated trace

Traced input: nums = [1, 2, 3] → [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. Original problem: neetcode.io/problems/subsets

Complexity

BestO(n·2ⁿ)

AverageO(n·2ⁿ)

WorstO(n·2ⁿ)

SpaceO(n)

2ⁿ subsets, each copied in O(n). Recursion depth n.

Key idea

Every node of the recursion tree is a subset, so add the path on entry.
start ensures elements are picked in increasing index order.
Add, recurse, remove: the path is restored for the next choice.
Bitmasks from 0 to 2ⁿ−1 are an iterative alternative.

Common mistakes

Adding path itself instead of a copy: every result ends up empty.
Starting the loop at 0 instead of start creates duplicates.

Solution

Java

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

Python

def subsets(nums: List[int]) -> List[List[int]]:
    res = []

    def backtrack(start: int, path: List[int]) -> None:
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return res

C++

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    backtrack(nums, 0, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty input The empty set is still a subset.	`nums = []`	`[[]]`
Single element Take it or don't.	`nums = [0]`	`[[], [0]]`
Negative values Values don't matter, only positions.	`nums = [-1, 2]`	`[[], [-1], [-1, 2], [2]]`