Subsets

You are given an array nums of distinct integers. Return every possible subset of it (its power set), including the empty subset and the whole array.

Each subset must appear exactly once. The subsets may be listed in any order, and the numbers inside a subset may also be in any order: [5, 1] and [1, 5] count as the same subset, so only one of them may appear.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Backtracking · problem 121 of 169

Start simple

Count from 0 to 2ⁿ − 1 and use the bits of each number to decide which elements to include: O(n · 2ⁿ), which is already optimal because the output has that size.

The key idea

A subset is fully described by a yes/no decision for each element, so there are exactly 2ⁿ of them, and any algorithm must spend at least that long just writing them out. The goal is to generate each one exactly once without duplicates.

Backtracking does that with a decision tree. A recursive helper build(start) first records the current subset, then for each index i >= start adds nums[i], recurses with start = i + 1, and removes it again. Because each recursive call only looks at indices after the last chosen one, every subset is produced in exactly one order (increasing index), so [1, 5] can never appear a second time as [5, 1].

Record a copy of the current list: the same list object is modified as the search continues. Undoing the change after the recursive call (the “backtrack” step) restores it for the next branch.

Complexity

• Time: O(n · 2<sup>n</sup>)
• Space: O(n) recursion, plus the output

Python

class Solution:
    def subsets(self, nums):
        result = []
        current = []

        def build(start):
            result.append(current[:])          # record a copy of this subset
            for i in range(start, len(nums)):
                current.append(nums[i])        # choose nums[i]
                build(i + 1)                   # only later elements may follow
                current.pop()                  # undo the choice

        build(0)
        return result

JavaScript

var subsets = function(nums) {
  const result = [];
  const current = [];

  const build = (start) => {
    result.push([...current]);          // record a copy of this subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);            // choose nums[i]
      build(i + 1);                     // only later elements may follow
      current.pop();                    // undo the choice
    }
  };

  build(0);
  return result;
};

What the interviewer is checking

This is the canonical backtracking template; interviewers check that you can generate a combinatorial space without duplicates and reason about output-sized complexity.

Mistakes to avoid

• Appending the working list itself instead of a copy, so every recorded subset ends up identical (usually empty).
• Forgetting the empty subset.
• Restarting the loop at index 0 in each call, which creates duplicates like [1, 5] and [5, 1].

Follow-ups to expect

• What if nums contains duplicates? (Sort, skip equal siblings.)
• Only subsets of size k? (Stop recursion at size k.)
• Generate them lazily one at a time? (Iterate a bitmask counter.)

In real software

Enumerating subsets appears in feature-selection searches, testing every combination of configuration flags, and exact solvers for small knapsack or set-cover instances.

Practice next