Subsets
Include or exclude each element in turn; every leaf of that binary tree is one subset, 2^n in all.
Decision · step 2 of 24Enumeration: All subsets of three
Element 0 is 1. First branch: include it, chosen is now {1}. Go deeper.
What you will see
A binary decision tree; each leaf is one subset.
Cost
| Best | O(2^n) |
|---|---|
| Average | O(2^n) |
| Worst | O(2^n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Each node of the decision tree announces the choice made and whether it led to success, failure or further choices.
Reduced motion: Tree nodes appear and grey out in place; no travelling focus.
Before this
Related
Taught by the same lesson
Enumeration covers these too, in the same run.