← Back to DSA Animator
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
Variables
curr
[ ]
start
1
need more
—
total found
0
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.