- Recursion is great when you can break the problem down into a smaller version of itself that ultimately reaches a base case, like whittling down a list or possibilities.
- Generating combinations with recursion aligns well with the idea of "taking it" or "leaving it" and recursively calling for each of those cases.
- Definition: Selection of items where the order does not matter.
- Example: Choosing 2 books to take on vacation from a shelf of an adventure book, a mystery book, and a romance book ([adventure, mystery] is the same as [mystery, adventure]).
- Use Case: Generating subsets of a set.
- Mnemonic: Combinations => Choice
- Definition: Arrangement of items where the order does matter.
- Example: Arranging 3 books on a shelf from a collection of an adventure book, a mystery book, and a romance book ([adventure, mystery, romance] is different from [mystery, adventure, romance]).
- Use Case: Generating all possible orderings of a set.
- Mnemonic: Permutations => Position
- Subset Sum
- All Subsets
- HT Permutations
- Partition Number