Hack Hour Strategy - Recursions in Combinations

Why Recursion for Combinations?

• 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.

Combinations vs Permutations

Combinations

• 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

Permutations

• 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

Challenges

1. Subset Sum
2. All Subsets
3. HT Permutations
4. Partition Number