LeetCode #78 Easy

Subsets (Power Set)

Return all subsets (the power set) of an array of distinct integers — 2ⁿ of them.

backtrackingbit-manipulation

02

Intuition

💡

Every subset is a chain of n independent yes/no decisions: include this element or not. Backtracking walks that decision tree — take the element, recurse, un-take it, recurse — and every leaf is one subset. Equivalently, each n-bit number 0..2ⁿ−1 is a subset: bit i set means take nums[i].

03

Approach

1

Include / exclude recursion

dfs(i, path): at each index, branch on taking nums[i] or skipping it; at i == n, snapshot path. 2ⁿ leaves = 2ⁿ subsets.

2

Snapshot every node instead

The common variant records path on entry and only branches on which later element to add next — same output, no explicit base case.

3

Bitmask alternative

for mask in range(2**n): build the subset from set bits. Iterative, no recursion, same O(n·2ⁿ).

04

Solution & live demo

python

▶1class Solution:
▶2    def subsets(self, nums):
▶3        res, path = [], []
▶4        def dfs(i):
▶5            res.append(path[:])         # snapshot current choices
▶6            for j in range(i, len(nums)):
▶7                path.append(nums[j])    # choose
▶8                dfs(j + 1)
▶9                path.pop()              # un-choose
▶10        dfs(0)
▶11        return res

05

Edge cases

Empty input

Power set is [[]] — one empty subset.

Result must contain [] and the full set

The all-skip and all-take branches produce them.

path must be copied

Append path[:], not path — the list mutates during backtracking.

06

Complexity

Time

O(n · 2ⁿ)

Space

O(n)

2ⁿ subsets, each up to n long; recursion depth n.