AlgoScope

Subsets

Include or exclude each element in turn. Every leaf of that binary tree is one subset, 2^n in all.

Backtracking, algorithm, intermediateAlso called power set
Include 1 and recurse.102132i
Include 1 and recurse.102132i

Enumeration: All subsets of three

Decision, step 2 of 24

Element 0 is 1. First branch: include it, chosen is now {1}. Go deeper.

Cost

Best
O(2^n)
Average
O(2^n)
Worst
O(2^n)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Enumeration covers these too, in the same run.