Skip to main content

58. Subsets

mediumAsked at Datadog

Return all subsets of a distinct-integer array (the power set). Datadog uses this as a backtracking foundation, and probes you to discuss bitmask enumeration as an alternative.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite backtracking question.

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 doubling

Start with [[]]. For each value v, append v to a copy of every existing subset and add to the result.

Time
O(n * 2^n)
Space
O(n * 2^n)
function subsets(nums) {
  let out = [[]];
  for (const v of nums) {
    const more = out.map(s => [...s, v]);
    out = out.concat(more);
  }
  return out;
}

Tradeoff: Clean and short. Datadog accepts this — it's iterative backtracking with implicit structure.

2. Backtracking with start index (optimal)

Recurse; at each level, choose to include or exclude. Emit the current path at every step.

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: Canonical backtracking template. Emitting at every level (not just leaves) covers all subsets including the empty set.

Datadog-specific tips

Datadog will probe with: 'What if n is large?' At n > 25, 2^n explodes. Mention the bitmask enumeration approach: iterate 0..2^n - 1, treat each as a bitmask selecting elements. Same complexity but no recursion overhead.

Common mistakes

  • Emitting only at the recursion base case — produces only the full set.
  • Pushing path without copy — out gets shared references.
  • Iterating 0..2^n on n=10 in a hot loop without realizing 2^30 is over a billion — fine for n=10 but adversarial inputs break.

Follow-up questions

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

  • Subsets II (LC 90) — with duplicates; skip equal siblings.
  • Power Set with bitmasks — non-recursive variant.
  • Combinations (LC 77) — fixed size k.

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 emit at every recursion level?

Every node in the recursion tree corresponds to a unique subset (defined by the current path). Emitting at every level captures all 2^n subsets.

Bitmask variant?

for (let mask = 0; mask < 1 << n; mask++) — for each bit set, include the corresponding element. O(n * 2^n) same as backtracking but iterative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →