Counting Principles
The sum rule and product rule. When to add vs when to multiply. The foundation for all combinatorics.
Lessons
1. Intro
(The Goal)
2. Why Counting Matters
(Algorithms need to know how many)
3. The Sum Rule
(Add when choices are separate)
4. Sum Rule Example
(Choosing a programming language)
5. The Product Rule
(Multiply when choices are independent)
6. Product Rule Example
(Building a username)
7. When to Add vs Multiply
(The decision framework)
8. Mixed Example
(Combining both rules)
9. Problem - Count Passwords
(Simple product rule application)
10. Password Count - Solution
(26^4 = 456,976)
11. Password Variants
(Adding constraints)
12. Counting Paths on Grids
(Classic DP problem)
13. Counting Strings
(Character combinations)
14. Counting with Restrictions
(Exclude certain cases)
15. At Least One Constraint
(Common restriction pattern)
16. Double Counting Principle
(Count the same set two ways)
17. Pigeonhole Principle
(More items than containers)
18. Pigeonhole Example
(Identical hash values)
19. Inclusion-Exclusion Principle
(Count overlapping sets)
20. Inclusion-Exclusion Example
(Students in clubs)
21. Counting in Practice
(Real algorithm problems)
22. What Comes Next
(Ordered counting)
23. Overcounting and Correction
When simple rules fail
24. Counting Subsets
The power of 2
25. Counting Binary Strings
Direct application
26. Counting with Forbidden Positions
Subtract what you cannot use
27. Counting Divisors
Using prime factorization
28. Problem - Climbing Stairs
Counting paths with steps
29. Climbing Stairs - Insight
Recursive structure
30. Climbing Stairs - Implementation
The pseudocode
31. Problem - Unique Paths
(LeetCode 62 - Grid paths)
32. Unique Paths - The Formula
(Sum of incoming paths)
33. Unique Paths - Implementation
(2D DP table)
34. Lessons from Unique Paths
(Grid counting principles)
35. Problem - Unique Paths II
(LeetCode 63 - Obstacles)
36. Unique Paths II - Handling Obstacles
(Setting blocked cells to 0)
37. Unique Paths II - Implementation
(Modified DP with checks)
38. Lessons from Unique Paths II
(Counting with constraints)
39. Problem - Letter Combinations
(LeetCode 17 - Product rule)
40. Letter Combinations - Counting First
(Product rule application)
41. Letter Combinations - Implementation
(Backtracking generation)
42. Lessons from Letter Combinations
(Product rule in practice)
43. Section Recap
What we learned