Skip to main content

58. Subsets

mediumAsked at Workday

Return all possible subsets of a set of distinct integers. Workday uses this for power-set generation — same shape as enumerating all possible permission-flag combinations in an RBAC role.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday RBAC team — direct analogy.

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 new element, double the result by adding the element to each existing subset.

Time
O(n * 2^n)
Space
O(n * 2^n)
let res = [[]];
for (const x of nums) { res = res.concat(res.map(s => [...s, x])); }
return res;

Tradeoff: Elegant one-liner.

2. Backtracking

Recurse with index. At each step, include current subset and try adding each remaining element.

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

Tradeoff: Backtracking template — extends naturally to subsets-with-duplicates and constraints.

Workday-specific tips

Workday accepts either. The iterative-doubling version is shorter; the backtracking is what they'll ask you to extend to Subsets II (with duplicates). Walk through both if you have time.

Common mistakes

  • Pushing current without copying — all subsets share the same mutating array.
  • Off-by-one with start index — generates duplicates.
  • Forgetting the empty subset.

Follow-up questions

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

  • Subsets II (LC 90) — with duplicates.
  • Combinations (LC 77) — fixed-size subsets.
  • Bitmask enumeration of all 2^n subsets.

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 2^n subsets?

Each element is either in or out of a subset. n binary choices = 2^n possibilities.

Bitmask alternative?

For i from 0 to 2^n-1, generate subset by including nums[k] if bit k of i is set. Constant overhead per subset.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →