Subsets
Include or exclude each element in turn. Every leaf of that binary tree is one subset, 2^n in all.
Enumeration: All subsets of three
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)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Enumeration covers these too, in the same run.