剑指 Offer II 080. 含有 k 个元素的组合 #

标签：数组、回溯
难度：中等

题目大意 #

给定两个整数 n 和 k。

要求：返回范围 [1, n] 中所有可能的 k 个数的组合。可以按任何顺序返回答案。

解题思路 #

组合问题通常可以用回溯算法来解决。定义两个数组 res、path。res 用来存放最终答案，path 用来存放当前符合条件的一个结果。再使用一个变量 start_index 来表示从哪一个数开始遍历。

定义回溯方法，start_index = 1 开始进行回溯。

如果 path 数组的长度等于 k，则将 path 中的元素加入到 res 数组中。
然后对 [start_index, n] 范围内的数进行遍历取值。
- 将当前元素 i 加入 path 数组。
- 递归遍历 [start_index, n] 上的数。
- 将遍历的 i 元素进行回退。
最终返回 res 数组。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    res = []
    path = []

    def backtrack(self, n: int, k: int, start_index: int):
        if len(self.path) == k:
            self.res.append(self.path[:])
            return
        for i in range(start_index, n - (k - len(self.path)) + 2):
            self.path.append(i)
            self.backtrack(n, k, i + 1)
            self.path.pop()

    def combine(self, n: int, k: int) -> List[List[int]]:
        self.res.clear()
        self.path.clear()
        self.backtrack(n, k, 1)
        return self.res