DSA AnimatorDSA animations
Combinations LC #77 Medium Backtracking · Pruning
Problem

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.

Example 1
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: C(4,2) = 6 combinations.
Example 2
Input: n = 1, k = 1
Output: [[1]]
Constraints: 1 ≤ n ≤ 20  |  1 ≤ k ≤ n
Try Examples
Custom:
Approach
Backtracking with Pruning Bound
Choose k numbers from [1..n] ascending. Pruning: loop only up to n-(k-curr.size)+1 — if fewer elements remain than needed, stop early.
Number Range [1..n]
Current Combination
curr = [ ] (empty)
Results 0 found
Recursion Tree
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Choose k numbers from 1..n (order doesn't matter)
2
Loop from start to pruning bound: n-(k-curr.size)+1
3
Base case: curr.size()==k → add to results
4
C(n,k) total combinations
Time
O(C(n,k)·k)
Space
O(k)
Why Backtracking Works

Standard k-combination backtracking. The pruning bound n-(k-curr.size)+1 avoids branches that can never reach k elements — if fewer candidates remain than needed, stop early. Since we go in ascending order (start=i+1), no duplicate combinations arise.

How to solve Combinations

LeetCode 77 · Medium · Backtracking · Pattern: Backtracking + Pruning

Why the obvious approach is slow

Generating every subset and keeping those of size k wastes work. Stop as soon as a path has k numbers.

The key idea

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.

Remember

Increasing order avoids repeats. Prune when not enough numbers are left.

Run the animation above on your own input, or watch the 1:15 video explanation of Combinations with a dry run and Java code.

More Backtracking problems