Subsets

Examples

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

There are 2^3 = 8 ways to include or exclude each of the three numbers.

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

A single number has exactly two subsets: empty, and itself.

Constraints

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

• All numbers in nums are unique.

Approach

The most direct way to see every subset is to literally try, for each number, both of its two fates - included or excluded - and see where each combination of choices leads.

One brute-force way to do this is to line up all 2^n combinations of yes/no decisions (for n numbers, one "in or out" decision per number) and read them off directly - each combination of decisions describes exactly one subset.

A more natural way to explore the same set of choices is to build one subset at a time: pick a number, decide to include it, and move on to the next number. Once you've explored every path that starts with "included", undo that choice (remove the number) and explore every path that starts with "excluded" instead. Trying a choice, exploring everything that follows from it, and then undoing it to try the next choice is the core idea behind backtracking - and it naturally visits every subset exactly once.

Solutions

Brute Force — Bitmask Enumeration

Every subset corresponds to a unique sequence of "include" / "exclude" decisions, one per number - and a sequence of n yes/no decisions is exactly what an n-bit binary number represents. Walk through every integer from 0 to 2^n - 1, and use its binary digits as instructions: if bit i is 1, include nums[i] in this subset.

function subsets(nums) {
  const n = nums.length;
  const result = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        subset.push(nums[i]);
      }
    }
    result.push(subset);
  }

  return result;
}

Time: O(2^n * n) · Space: O(2^n * n)

Optimal — Backtracking (Choose / Explore / Un-choose)

Build one subset at a time with a running list. At each number, first try including it (push it onto the current subset, recurse on the rest, then pop it back off), then try skipping it (just recurse on the rest, without ever adding it). Every time you reach the end of the list, the current running subset is complete - record a copy of it.

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

  function backtrack(index) {
    if (index === nums.length) {
      result.push([...current]);
      return;
    }

    // Choice 1: include nums[index]
    current.push(nums[index]);
    backtrack(index + 1);
    current.pop(); // undo the choice

    // Choice 2: skip nums[index]
    backtrack(index + 1);
  }

  backtrack(0);
  return result;
}

Time: O(2^n * n) · Space: O(n) auxiliary (recursion depth), plus O(2^n * n) for the output