DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Subsets

mediumRecursion Must-do

Problem statement

Given an array of distinct integers, return every possible subset of it, including the empty subset and the full array. Each subset should appear exactly once. The order of the subsets, and the order of values inside a subset, does not matter.

An array of n values has exactly 2^n subsets, because each value is either in or out.

Examples

Example 1

Input: nums = [4, 7]

Output: [[], [4], [7], [4, 7]]

Example 2

Input: nums = [1, 5, 9]

Output: [[], [1], [5], [9], [1, 5], [1, 9], [5, 9], [1, 5, 9]]

Explanation: Three values, so 2^3 = 8 subsets.

Hints

Approach

Backtracking builds the subsets as a decision tree. At depth i you decide whether nums[i] is in the current subset.

  1. dfs(i): if i == n, record a copy of path.
  2. Otherwise, append nums[i] to path, call dfs(i + 1), then pop it.
  3. Call dfs(i + 1) again without it.

The cost is the same as the bitmask version, because the output itself has n · 2^n numbers in it, so no method can do better. The value of backtracking is that it is the template for the harder variants: skipping equal neighbours for duplicate input, stopping early when a sum is exceeded, or limiting the subset size. Remember to append a copy of path, not path itself.

ComplexityTime O(n · 2^n)Space O(n) recursion depth besides the output
Python
class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
result, path = [], []
def dfs(i: int) -> None:
if i == len(nums):
result.append(path[:]) # copy, not the live list
return
path.append(nums[i]) # take nums[i]
dfs(i + 1)
path.pop() # skip nums[i]
dfs(i + 1)
dfs(0)
return result

Follow-up questions

  • Return only the subsets whose sum equals a target, stopping early when the sum is exceeded.
  • The input contains duplicates. Return each distinct subset once.

Frequently asked questions

You appended path itself instead of a copy. Every entry in the result points to the same list, and by the end the backtracking has popped everything off it. Use path[:] in Python or new ArrayList<>(path) in Java.

Sort the array first, then in the loop-style backtracking skip nums[i] when it equals nums[i - 1] at the same depth. That prevents generating the same subset twice.

Enumerating combinations of feature flags, config options or test matrix dimensions is subset generation. It is also the base pattern for every backtracking question, so interviewers use it to check that you can write clean recursion before moving on.