Coding interview problems › Backtracking

🧩 Backtracking Medium

Subsets (Power Set)

Subsets (power set) explained: the choose, explore, un-choose backtracking template for all 2^n subsets, with tested Python and a live recursion-tree visual.

Also searched as: power set backtracking · generate all subsets of an array · subsets recursion include exclude

🧩

Try it live Free

Backtracking: Subsets, Permutations & Pruning

Watch the recursion tree grow one call at a time, choose, explore, un-choose, as every one of the 2ⁿ subsets is generated.

Also useful: Recursion & the Call Stack

Open the playground →

The problem

Given a list of distinct integers, return every possible subset (the power set), including the empty set and the full set. The order of subsets does not matter.

Input[1, 2, 3]
Output[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

2^3 = 8 subsets

Input[0]
Output[[], [0]]

The key insight

Every element faces one yes-or-no question: in or out? Backtracking walks that decision tree. At each call the current partial subset is itself a valid answer, so record it, then try adding each later element, recurse, and undo the addition before trying the next one.

Brute force first: There is no shortcut around producing 2n subsets; the goal is to produce each exactly once without wasted work.

Step-by-step approach

  1. Keep a list path for the subset being built and a list out of answers.
  2. Define dfs(start): first append a copy of path to out.
  3. For each index i from start to the end: choose nums[i] (append it), explore with dfs(i + 1), then un-choose it (pop).
  4. Starting the loop at start means elements are only added in increasing index order, so no subset appears twice.
  5. Call dfs(0) and return out.

Python solution

PYTHON 3tested
def subsets(nums):
    out, path = [], []

    def dfs(start):
        out.append(path[:])            # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            dfs(i + 1)                 # explore
            path.pop()                 # un-choose

    dfs(0)
    return out

Complexity

TimeO(n · 2^n)
SpaceO(n)

There are 2n subsets and copying each costs up to O(n). Apart from the output, the recursion depth and path use O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of generating all subsets?

O(n × 2^n) time because there are 2^n subsets of average length n/2. Extra space is O(n) for the recursion and current path, plus the output.

How do I handle duplicates in the input (Subsets II)?

Sort the array first, and inside the loop skip nums[i] when i > start and nums[i] == nums[i - 1]. This stops the same value from starting two identical branches at the same level.

Is there a non-recursive way to generate subsets?

Yes. Use bitmasks: for every integer m from 0 to 2^n - 1, include nums[i] when bit i of m is set. Or start with [[]] and for each number append it to a copy of every existing subset.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Backtracking Backtracking: Subsets, Permutations & Pruning lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.