题目描述

[MEDIUM]

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:

1
2
3
4
Input: n = 4, k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

1
2
3
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Example 3:

1
2
Input: n = 2, k = 2
Output: [[1,2]]

Constraints:

1 <= n <= 20
1 <= k <= n

思路

We can solve this using backtracking:

  1. We build combinations incrementally.
  2. When the current combination reaches size k, we add it to the result.
  3. For each step, we choose a number i from the current position up to n, and recursively explore.

different from permutation: no need to keep track of used, and start position already resolve the case of [1,2] and [2,1]

Think of this as exploring a decision tree:

  • At each node, you choose the next number to include.
  • Stop when you have selected k numbers.
  • Backtrack (remove the last element) and try the next number.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> re;
    vector<int> com;

    void backtrack(int start, int n, int k) {
        // Base case: if we have k numbers
        if (com.size() == k) {
            re.push_back(com);
            return;
        }
        
        // Try every number from 'start' to 'n'
        for (int i = start; i <= n; i++) {
            com.push_back(i);         // choose
            backtrack(i + 1, n, k);    // explore
            com.pop_back();           // un-choose (backtrack)
        }
    }
    
    vector<vector<int>> combine(int n, int k) {
        backtrack(1, n, k);
        return re;
    }
};