解题思路

这就是一道回溯题

首先我们要理解什么是组合，一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。，在这题中，我们的m<n,所以每次都要向后一位遍历，不能重复。

回溯的结束条件就是k == len(temp)，我们要将temp添加进result

temp是临时数组，result是最终要输出的数组

这里有一个剪枝，当剩下所有元素都无法与temp组合成新的组合时直接返回。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(start, temp):
            if len(temp) == k:
                result.append(temp.copy())
                return
            elif n - start + len(temp) < k: return
            for i in range(start + 1, n + 1):
                temp.append(i)
                backtracking(i, temp)
                temp.pop()
        result = []
        temp = []
        backtracking(0, temp)
        return result

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> temp;
        vector<vector<int>> result;
        backtracking(n, k, 0, result, temp);
        return result;
    }

    void backtracking(int n, int k, int start, vector<vector<int>> &result, vector<int> temp) {
        // 结束条件
        if (temp.size() == k) {
            result.push_back(temp);
            return; // 回溯
        } else if (n - start + temp.size() < k) {
            return;
        }
        for (int i = start + 1; i < n + 1; ++i) {
            temp.push_back(i);
            backtracking(n, k, i, result, temp);
            temp.pop_back();
        }
    }
};

Go

func combine(n int, k int) [][]int {
	var result [][]int
	temp := make([]int, 0, 2)
	backtracking(n, k, 0, &result, temp)
	return result
}

func backtracking(n int, k int, start int, result *[][]int, temp []int) {
	if k == len(temp) {
		t := make([]int, k)
        copy(t, temp)
		*result = append(*result, t)
		return
	}
	for i := start + 1; i < n+1; i++ {
		temp = append(temp, i)
        if len(temp) + n - i < k {return}
		backtracking(n, k, i, result, temp)
		end := len(temp)
		temp = temp[:end-1]
	}
}