Combinations
The key idea
Build each combination by picking numbers in increasing order. At each step only consider values greater than the last one picked, so [1,2] is generated but the duplicate [2,1] never is. Recurse, record a result when the partial list reaches length k, then backtrack to try the next choice.
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.
Constraints
1 <= n <= 201 <= k <= n
Examples
Input: n = 3, k = 2
Output: [[1,2],[1,3],[2,3]]
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Input: n = 1, k = 1
Output: [[1]]
Complexity
Time: O(k * C(n, k)) Space: O(k)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM
- PermutationsMEDIUM