Basic example
Input
n = 4, k = 2
Output
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
All 2-number combinations from 1..4 in lexicographic order.
Full lesson preview
Generate combinations of k numbers
Generate all k-sized combinations from numbers 1..n using backtracking.
Python practice15 minRecursion & BacktrackingIntermediateLast updated March 27, 2026
Problem statement
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. Each combination should be in ascending order and the list of combinations should follow lexicographic order (first by the first element, then second, etc.). If k == 0, return a list containing the empty combination: [[]]. If k > n return an empty list []. Use backtracking to build combinations efficiently.
Task
Implement a backtracking function that returns all combinations of k numbers chosen from 1..n in lexicographic order.
Examples
Input format
Two integers n and k. You will call generate_combinations(n, k).
Output format
A list of lists, each inner list is a combination. Example: [[1,2],[1,3]].
Constraints
0 <= k <= n <= 20. The number of combinations can grow rapidly; ensure your algorithm uses backtracking to prune work.
Samples
Sample 1
Input
n = 1, k = 1
Output
[[1]]
Only one possible combination.