Skip to main content

78. Subsets

medium

Return every possible subset (the power set) of a list of distinct integers. The cleanest demonstration of the include/exclude binary recursion tree and a foundational backtracking pattern.

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

Two mental models — both yield the same result: (a) for each element, include or exclude, (b) for each index i, pick zero or more later elements to append.

Hint 2

Recursion tree has 2^n leaves. Each leaf is a subset.

Hint 3

Backtrack with a current path. At index i: push the current path (it represents a valid subset), then for each j in [i, n), include nums[j], recurse to j+1, and pop.

Hint 4

Push the empty subset first, then build.

Solution approach

Reveal approach

Use a depth-first backtracking helper that takes the start index and a current path. At every entry, snapshot the path to the result (because every node in the recursion tree, not just leaves, is a valid subset). Then loop j from start to nums.length - 1: append nums[j], recurse with start = j + 1, pop. The 'start' parameter is what prevents duplicates — by only considering later indices, you never form the same combination in a different order. Total subsets = 2^n. Time is O(n * 2^n) for generating and copying every subset; space is O(n) for the recursion stack plus O(n * 2^n) output.

Complexity

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

Related patterns

  • backtracking
  • recursion
  • power-set

Related problems

Asked at

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

  • Amazon
  • Meta
  • Google
  • Bloomberg
  • Microsoft

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →