Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Subsets

LeetCode #78Medium

Every node of the tree is a subset

Given an array of distinct integers, return all possible subsets (the power set), with no duplicate subsets in the result.

Asked atAmazonMetaGoogle

Backtracking · extend with later elements

time O(2ⁿ · n)space O(n)

step 1 / 17

solution-space tree

{1,2,3}

{1,2}

{1,3}

{1}

{2,3}

{2}

{3}

{ }

subsets found

(none yet)

Backtracking · extend with later elements


▸
1subsets(start, path):
2    record path                 // every node is a subset
3    for i in start..n−1:
4        path.push(arr[i])       // choose
5        subsets(i+1, path)      // explore
6        path.pop()              // un-choose (backtrack)

state

input[1, 2, 3]

line 1Generate EVERY subset of [1, 2, 3]. Backtracking builds them by extending a partial subset with later elements. Each node in this tree is one partial subset; exploring the whole tree visits every subset exactly once.