Combinations
A combination is a subset with a size cap, and that's the whole trick. You reuse the same start index from subsets because order still doesn't matter, but you only record once the selection hits exactly k elements. Where it gets interesting is Combination Sum, where you're chasing a target value instead of a fixed count and pruning is what keeps the search from exploding.
Combinations: Choose k elements from n, where order doesn't matter.
From [1, 2, 3, 4], choose 2: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]
That's C(4,2) = 6 combinations. Not 12 (permutations) because [1,2] = [2,1].
From [1, 2, 3, 4], choose 2: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]
That's C(4,2) = 6 combinations. Not 12 (permutations) because [1,2] = [2,1].
What's inside
- 1 problem, worked step by step
- about 25 min
Premium lessonData Structures & Algorithms
Keep going with Premium.
All 78 lessons and 103 worked problems in this course, plus what 100 companies ask, pulled from 20,000+ candidate reports.
100 companies. Checked every month.
Unlock the full course$49 a year · less than $1 a week · Cancel anytime