Coding problem · Medium · Backtracking

Subsets

Medium Algorithms & data structures Seen at Meta, Amazon, Bloomberg

Given an array nums of distinct integers, return all possible subsets (the power set), in any order, without duplicates.

Example 1

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

Example 2

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

Hints

Hint 1

For each element, you either include it or not — 2ⁿ subsets.

Hint 2

Backtrack: choose, recurse, un-choose.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n · 2ⁿ) · Space O(n) recursion (excluding output)

Backtracking: at index i, record the current subset, then for each later element add it, recurse, and remove it. Each of the 2ⁿ subsets is produced once. An iterative alternative: start with [[]] and, for each number, append it to copies of every existing subset.

Reference solution

function subsets(nums) {
  const out = [];
  const cur = [];
  const go = (i) => {
    out.push([...cur]);
    for (let j = i; j < nums.length; j++) {
      cur.push(nums[j]);
      go(j + 1);
      cur.pop();
    }
  };
  go(0);
  return out;
}

function subsets(nums: number[]): number[][] {
  return nums.reduce<number[][]>((acc, x) => acc.concat(acc.map((s) => [...s, x])), [[]]);
}

def subsets(nums: list[int]) -> list[list[int]]:
    out: list[list[int]] = []
    cur: list[int] = []

    def go(i: int) -> None:
        out.append(cur[:])
        for j in range(i, len(nums)):
            cur.append(nums[j])
            go(j + 1)
            cur.pop()

    go(0)
    return out

<?php

function subsets(array $nums): array
{
    $out = [[]];
    foreach ($nums as $x) {
        foreach ($out as $s) {
            $out[] = [...$s, $x];
        }
    }
    return $out;
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        go(nums, 0, new ArrayList<>(), out);
        return out;
    }

    private void go(int[] nums, int i, List<Integer> cur, List<List<Integer>> out) {
        out.add(new ArrayList<>(cur));
        for (int j = i; j < nums.length; j++) {
            cur.add(nums[j]);
            go(nums, j + 1, cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

Follow-up questions

Subsets II: input with duplicates (sort, skip equal siblings).

Permutations · Medium