Subsets

Approach Summary

At each index, two choices: include or exclude. Backtrack by adding element, recursing, removing element.

Full Solution & Approach

Subsets are generated by a backtracking recursion that builds the answer incrementally. Define a recursive helper that takes a start index and a working path. At every call, record a copy of the current path into the results — this captures the subset for every prefix of choices. Then loop from start to the end, appending each element, recursing with i + 1, and popping it back off after (the backtrack). Because each element is either included or excluded relative to the recursion tree, every subset appears exactly once. The number of subsets is 2ⁿ, and each subset has length at most n, so the output size bounds the complexity: O(n · 2ⁿ) time and space. The same choose → recurse → unchoose skeleton generates permutations, combinations, and subsets.

There are 2ⁿ subsets, each costing up to O(n) to copy — O(n · 2ⁿ) time. The recursion stores the path (depth ≤ n) plus the 2ⁿ subsets in the output — O(n · 2ⁿ) space.

Solution Code

Solution

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

function subsets(nums) {
  const res = [];
  const path = [];
  function backtrack(start) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1);
      path.pop();
    }
  }
  backtrack(0);
  return res;
}

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

private 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);
    }
}

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

Edge Cases to Watch

Empty input — returns [[]] (the empty subset)
Duplicate values — subsets are still distinct by position, e.g. [1] appears twice for [1, 1]
Single element — [[], [x]]
Large n — 2ⁿ explodes; problem constraints keep n around 10–20

How to Recognize This Pattern

Generate all subsets/power set
Include/exclude pattern

Complexity Analysis

Time Complexity

O(n × 2ⁿ)

Space Complexity

O(n)