BacktrackingRecursion & Backtracking

Subsets (include / exclude)

Enumerate all 2^n subsets of a set by deciding, for each element in turn, whether to include it.

Items — Up to 4 distinct numbers, e.g. "1, 2, 3"

Call stack (top first)

empty

Subsets found (0 / 8)

empty

1/31Enumerate all subsets of [1, 2, 3]. Each element is either in or out, so there are 2^3 = 8 subsets and the recursion tree is a full binary tree.

Call on the stackCall returnedElement in current subset

PseudocodeLearn Subsets (Power Set) →

1go(i, current):
2  if i == n: record(current); return
3  current.push(a[i]); go(i+1, current)   // include a[i]
4  current.pop()                          // undo (backtrack)
5  go(i+1, current)                       // exclude a[i]

Variables

Complexity

worst O(n · 2^n)

space O(n)

Speed