Skip to main content

58. Subsets

mediumAsked at Vercel

Return all possible subsets of a distinct-integer array. Vercel asks this for the include-or-skip backtracking pattern — same shape as enumerating valid feature-flag combinations for their canary configuration system.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel screen; backtracking expected.
  • Blind (2026-Q1)— Listed in Vercel platform engineer screen.

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

Examples

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]]

Approaches

1. Iterative growth

Start with [[]]. For each new element, double the result by adding 'with this element' versions.

Time
O(n * 2^n)
Space
O(n * 2^n)
function subsets(nums) {
  let out = [[]];
  for (const n of nums) {
    const next = [...out];
    for (const s of out) next.push([...s, n]);
    out = next;
  }
  return out;
}

Tradeoff: Doubles allocation per element. Clean but allocates intermediate arrays.

2. Backtracking with start index (optimal)

DFS with start index; at each call, push current path as a subset, then try extending with each element from start onward.

Time
O(n * 2^n)
Space
O(n) recursion
function subsets(nums) {
  const out = [];
  function dfs(start, path) {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1, path);
      path.pop();
    }
  }
  dfs(0, []);
  return out;
}

Tradeoff: Push every state (not just leaves) because every node IS a valid subset. The start-index dedup keeps subsets in non-decreasing-index order.

Vercel-specific tips

Vercel grades the backtracking version. Bonus signal: explaining that EVERY recursion node is a valid subset (push at the top, then branch) — distinguishing this from Combinations (LC 77) where only leaves count. Mention bitmask enumeration (2^n bitmasks) as a third elegant option.

Common mistakes

  • Pushing only at the leaf — misses all the proper subsets.
  • Forgetting the start index — produces duplicate subsets like [1,2] and [2,1].
  • Using `path` instead of `[...path]` — pushes a reference that mutates.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Subsets II (LC 90) — with duplicates; dedup with sort + skip.
  • Combinations (LC 77) — fixed-size subsets.
  • Bitmask enumeration — iterate 0..2^n and pick included indices.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why push at every node, not just leaves?

Every state of the path is a valid subset — including the empty path. Each recursion call represents 'I've decided the first k elements; here's a subset using those choices.'

Bitmask alternative?

Iterate 0..2^n - 1; for each mask, include nums[i] iff (mask & (1 << i)). Same complexity, no recursion. Cleaner for small n.

Practice these live with InterviewChamp.AI

Drill Subsets and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →