组合

题目要求：

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2

输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

题目思路：

3

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 先把不符合条件的情况去掉
        if n <= 0 or k <= 0 or k > n:
            return []
        res = []
        self.__dfs(1, k, n, [], res)
        return res

​

def dfs(self, start, k, n, pre, res):
# 当前已经找到的组合存储在 pre 中，需要从 start 开始搜索新的元素
# 在第 k 层结算
if len(pre) == k:
res.append(pre[:])
return

for i in range(start, n + 1):
pre.append(i)
# 因为已经把 i 加入到 pre 中，下一轮就从 i + 1 开始
# 注意和全排列问题的区别，因为按顺序选择，因此无须使用 used 数组
self.dfs(i + 1, k, n, pre, res)
# 回溯的时候，状态重置
pre.pop()

​