59. Subsets

Q: Why push at every recursion, not just leaves?

The 'path' at each recursion is a valid subset. The empty path is the empty subset; mid-recursion paths are non-empty subsets; leaf is the full set.

Q: When prefer bitmask?

When n is small (<= 30) and you want to parallelize. Each integer encodes a subset; you can shard the work.

mediumAsked at Plaid

Return all possible subsets (the power set) of a distinct-integer array. Plaid asks this as a combinatorial-generation warm-up before harder subset-sum reconciliation problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE II OA.
LeetCode Discuss (2026)— Plaid backtracking baseline.

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. Bitmask

Iterate every integer from 0 to 2^n - 1; include nums[i] when bit i is set.

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

function subsets(nums) {
  const n = nums.length;
  const out = [];
  for (let m = 0; m < (1 << n); m++) {
    const s = [];
    for (let i = 0; i < n; i++) if (m & (1 << i)) s.push(nums[i]);
    out.push(s);
  }
  return out;
}

Tradeoff: Clean enumeration. Limited to n <= 30 due to bit width, but the LC bound is 10.

2. Backtracking

DFS. At each step, push the current path, then try each later index.

Time: O(n * 2^n)
Space: O(n) recursion + 2^n output

function subsets(nums) {
  const out = [];
  function bt(start, path) {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      bt(i + 1, path);
      path.pop();
    }
  }
  bt(0, []);
  return out;
}

Tradeoff: Standard backtracking template. The 'push path on every recursion' (not just at leaves) is what makes this generate all subsets, not just full-length ones.

Plaid-specific tips

Plaid uses this to verify your backtracking template. Bonus signal: discuss the bitmask alternative as a stretch — useful when n is small and you want to parallelize across subsets.

Common mistakes

Only pushing path at the base case — generates only the leaves, missing intermediate subsets.
Forgetting [...path] — every subset ends up pointing to the same array.
Starting i from 0 inside backtrack — produces duplicate subsets.

Follow-up questions

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

Subsets II (LC 90) — with duplicates.
Generate all permutations (LC 46).
Subset sum (LC 416) — DP, not enumeration.

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 recursion, not just leaves?

The 'path' at each recursion is a valid subset. The empty path is the empty subset; mid-recursion paths are non-empty subsets; leaf is the full set.

When prefer bitmask?

When n is small (<= 30) and you want to parallelize. Each integer encodes a subset; you can shard the work.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →