Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 4:22
Generating Subsets and Permutations
Three ways to list every subset: counting bitmasks from 0 to 2^n - 1 like an odometer, the take-or-leave recursion, and the Gray code i ^ (i >> 1), where one item changes per step so a running total updates in constant time (prices 2, 5 and 7 hit a target of 7 twice; on 24 items the Gray walk was dozens of times faster than recomputing every sum). Then std::next_permutation in three moves (pivot, swap, reverse the tail), why aabc gives 12 arrangements and not 24, why you must sort first, and a measured table of how far listing goes.
You will learn
- Enumerate all subsets of n items with a bitmask loop or with take-or-leave recursion, and state the O(2^n * n) cost.
- Use the Gray code g = i ^ (i >> 1) to visit subsets so that consecutive ones differ by one item, updating a running value in O(1).
- Explain how std::next_permutation finds the next arrangement (pivot, swap, reverse) and why it lists distinct arrangements of a multiset only from sorted input.
- Judge from n whether listing subsets (up to about 20 to 25 items) or permutations (up to about 10 or 11) is feasible.