Subsets

The problem. Given an array nums of distinct integers, return all possible subsets (the power set). The answer must not contain duplicate subsets, in any order.

Example

nums = [1, 2, 3]  ->  [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
nums = [0]        ->  [[], [0]]

The pattern: subsets and combinations

Every problem in this chapter chooses some items where order doesn't matter: all subsets, subsets without duplicates, k numbers out of n, numbers that add up to a target, letters for each digit. The decision tree either asks take or skip? for each item, or loops over the items from a start index onwards so the same group is never built in two orders. Pruning — stopping when the sum is already too big, or too few items are left — keeps the tree small.

1. Build up level by level

Start with just the empty subset. For each number, copy every subset you have so far and add the number to the copy. Each number doubles the list.

1function subsets(nums) {2  let result = [[]];3  for (const x of nums) {4    result = [...result, ...result.map((s) => [...s, x])];   // every subset, with and without x5  }6  return result;7}

Time O(n · 2ⁿ), space O(n · 2ⁿ) — that's the size of the answer itself.

2. Backtracking: take or skip

1function subsets(nums) {2  const result = [];3  const path = [];4  const decide = (i) => {5    if (i === nums.length) {                 // every number decided: one subset6      result.push([...path]);7      return;8    }9    path.push(nums[i]);                      // take nums[i]10    decide(i + 1);11    path.pop();                              // un-take it ...12    decide(i + 1);                           // ... and skip it13  };14  decide(0);15  return result;16}

Time O(n · 2ⁿ): 2ⁿ leaves, each copied in O(n). Space O(n) for the path and the call stack, besides the output.

3. Bitmasks

Number the subsets 0 to 2ⁿ − 1. In binary, bit j of the number says whether nums[j] is in that subset — the decision tree flattened into counting.

1function subsets(nums) {2  const result = [];3  for (let mask = 0; mask < 1 << nums.length; mask++) {4    result.push(nums.filter((_, j) => mask & (1 << j)));   // bit j on: nums[j] is in5  }6  return result;7}

Time O(n · 2ⁿ), space O(1) besides the output. Neat for n up to about 20.

Comparing the approaches

Edge cases to test

Variations