Skip to main content

78. Subsets

medium

Enumerate every subset of a unique-element array (the power set). The bitmask approach maps every integer from 0 to 2^n - 1 to a subset — clean, iterative, no recursion stack.

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

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]]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

There are exactly 2^n subsets. With n <= 10 that's at most 1024.

Hint 2

Each subset corresponds to an n-bit binary mask: bit i set means include nums[i].

Hint 3

Iterate mask from 0 to (1 << n) - 1. For each mask, scan the bits and collect the elements at set positions.

Solution approach

Reveal approach

Bitmask enumeration. Let n = nums.length. For mask from 0 to (1 << n) - 1, build a subset by scanning bit positions: for i in 0..n-1, if (mask >> i) & 1 then push nums[i] into the current subset. Append the completed subset to the result list. The mapping is one-to-one: every subset corresponds to a unique mask, and every mask corresponds to a unique subset. Total work is 2^n masks × n bit-scans = O(n * 2^n) time, O(n * 2^n) total output space. The recursive backtracking solution has the same complexity but uses the call stack; bitmask iteration is cache-friendlier and avoids stack-depth concerns.

Complexity

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

Related patterns

  • bit-manipulation
  • backtracking

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Facebook

Practice these live with InterviewChamp.AI

Drill Subsets and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →