Skip to main content

62. Subsets

mediumAsked at Snowflake

Generate all 2^n subsets. Snowflake asks this to test bitmask vs backtracking enumeration — and to set up a discussion of bitmask DP for join-order optimization.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this to anchor bitmask DP discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad screens.

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 incremental

Start with [[]]. For each new number, duplicate every existing subset and append the new number to each copy.

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

Tradeoff: Clean iterative, no recursion. Allocates a new array per level — fine for n <= 10.

2. Bitmask enumeration (optimal)

Iterate i from 0 to 2^n - 1. For each i, the subset includes nums[j] iff bit j of i is set.

Time
O(n * 2^n)
Space
O(n * 2^n)
function subsets(nums) {
  const result = [];
  const n = nums.length;
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset = [];
    for (let j = 0; j < n; j++) {
      if (mask & (1 << j)) subset.push(nums[j]);
    }
    result.push(subset);
  }
  return result;
}

Tradeoff: Bitmask gives a constant-stack iteration — directly maps to bitmask DP for join-order optimization.

Snowflake-specific tips

Snowflake interviewers want both versions and your articulation of when bitmask wins (cache-friendly, no recursion). Bonus signal: pivot to Selinger join-order DP, which iterates over subsets of tables encoded as bitmasks — exact same enumeration.

Common mistakes

  • Backtracking variant pushing path directly without copy — shared mutation bug.
  • Bitmask iterating with 2 ** n in JS — fine up to n <= 53, but use 1 << n for clarity.
  • Forgetting the empty subset (must include []).

Follow-up questions

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

  • Subsets II (LC 90) — with duplicates.
  • Bitmask DP for join order.
  • How does Snowflake's planner enumerate join trees?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Bitmask or backtracking?

Bitmask is faster (constant-stack, cache-friendly) and trivially parallelizable. Backtracking is more flexible if you need pruning. For pure enumeration with n <= 20, bitmask wins.

How is this used in join-order DP?

Selinger's DP iterates over 2^n subsets of tables. For each subset, it computes the best plan to join those tables by considering all splits into two non-empty parts. The bitmask enumeration is the outer loop.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →