Skip to main content

78. Subsets

mediumAsked at Cisco

Subsets at Cisco tests the canonical backtracking pattern: pick-or-skip on each element. The interviewer is checking whether you write the recursion as 'include nums[i], recurse; exclude, recurse', and whether you correctly snapshot the current path on the way down rather than at the leaves.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II interview reports cite Subsets as a 30-minute backtracking round.
  • Blind (2025-10)— Cisco interview thread lists Subsets as a recurring problem.

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 bitmask

Each subset corresponds to a binary number 0..2^n - 1; bit i set = include nums[i].

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

Tradeoff: No recursion, deterministic order, clean to reason about. Limited to n <= 31 due to bit width, which fits LC's constraint (n <= 10) easily. Cisco interviewers respect this for its directness.

2. Backtracking (canonical)

DFS over indices. At each step, append the current path to the result, then for each later index, include + recurse + exclude.

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

Tradeoff: The canonical backtracking template — works as-is for Subsets II, Combinations, Permutations with minor tweaks. The 'append path then iterate' (NOT at the leaf only) is what gives you ALL 2^n subsets, not just the leaf ones.

3. Cascade / iterative growth

Start with [[]]. For each num, double the existing list by appending num to each existing subset.

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

Tradeoff: Easy to explain — 'each new number either is in or isn't in a subset, so the result doubles per added number.' Same Big-O. Three lines shorter than backtracking. Cisco interviewers love this when you can articulate the doubling invariant.

Cisco-specific tips

Cisco interviewers grade this on whether you SNAPSHOT the path with `[...path]` in backtracking — otherwise everyone in the result array references the SAME mutating array. Say it explicitly: 'I push a COPY of path because I'm going to mutate path with the next push/pop.' Pick any of the three approaches but lead with the backtracking template — it's the most general and extends to Subsets II (with duplicates) and Permutations.

Common mistakes

  • Pushing `path` (a reference) instead of `[...path]` (a snapshot) — every entry in result then mutates together and you end up with 2^n copies of the empty array.
  • Adding the path only at the LEAVES of the recursion — misses internal subsets and you end up with only the leaves (the singleton paths).
  • Off-by-one on `start` — must pass `i + 1` (not `i`) to the recurse to avoid duplicates.

Follow-up questions

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

  • Subsets II (LC 90) — input has duplicates; skip duplicates at the same recursion level.
  • Combinations (LC 77) — fixed-size subsets.
  • Permutations (LC 46) — order matters; use visited set instead of start index.
  • Letter Combinations of Phone Number (LC 17) — same pattern, different alphabet at each position.

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 snapshot the path?

Because we mutate `path` via push/pop across recursive calls. If we pushed the reference, every entry in result would point to the SAME array, which keeps changing. The snapshot freezes the current state. This is the #1 backtracking bug Cisco interviewers see — call it out before writing the line.

Bitmask, backtracking, or cascade — which to pick?

Bitmask is the shortest and most direct, but doesn't generalize to non-Subsets problems. Backtracking is the template that extends to Combinations and Permutations. Cascade is the easiest to explain verbally. Lead with backtracking on the whiteboard because Cisco interviewers often follow up with Subsets II or Permutations.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →