Given n and k, return all combinations of k numbers chosen from 1 to n. Order inside a combination does not matter.
DSA Animator › DSA Revision › Backtracking › Combinations
Remember: increasing order avoids repeats. Prune when not enough numbers are left. The video solves Combinations (LeetCode 77, Medium) with the Backtracking + Pruning pattern from the Backtracking topic, and you can replay every step in the interactive Combinations animation.
Given n and k, return all combinations of k numbers chosen from 1 to n. Order inside a combination does not matter.
For n equal to 4 and k equal to 2, there are 6 combinations. They are 1 2, 1 3, 1 4, 2 3, 2 4 and 3 4.
Generating every subset and keeping those of size k wastes work. Stop as soon as a path has k numbers.
Choose numbers in increasing order, starting after the last one picked. When the path has k numbers, record it and return. Prune: if too few numbers are left to reach k, stop the loop early.
Start with 1, then add 2, 3 and 4 in turn, recording 1 2, 1 3 and 1 4. Start with 2, recording 2 3 and 2 4. Start with 3, recording 3 4. Starting with 4 leaves no number after it, so that branch is pruned. There are 6 combinations.
In code, if the path size equals k, add a copy and return. Loop i from start while enough numbers remain, which is the pruning bound. Choose, recurse with i plus 1, then un-choose, so it's O of k times n choose k.
Remember: increasing order avoids repeats. Prune when not enough numbers are left.