Subsets / power set (recursion)

Medium TimeO(n · 2ⁿ) SpaceO(n)

A subset is any selection of the values, from none of them to all of them, and the collection of every one is the power set — three values give eight subsets. Given a list nums of distinct values, return every subset, the empty one and the complete list included. Order within a subset does not matter, and no subset appears twice.

Examples

Example 1

Input
nums = [1, 2, 3]
Output
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Each of the three values is in or out independently: 2 × 2 × 2 = 8 subsets.

Example 2

Input
nums = []
Output
[[]]
No values at all still has exactly one subset — the empty one, so the answer is not empty.

The Code

function subsets(nums) {
  if (nums.length === 0) return [[]];
  const first = nums[0];
  const rest = subsets(nums.slice(1));
  return [...rest, ...rest.map((s) => [first, ...s])];
}
subsets([1, 2, 3]);
Done
Step through subsets([1, 2, 3]) call by call

More like this

All backtracking examples (10) →