题目描述

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

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

思路解析

回溯，需要3个参数，temp代表当前组合情况，k代表还剩几个数完成条件，i代表从什么位置开始

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def backtrack(i, k, tmp):
            # 满足要去
            if k == 0:
                res.append(tmp)
                return 
            # 形成回溯
            for j in range(i, n + 1):
                backtrack(j+1, k-1, tmp + [j])
        backtrack(1, k, [])
        return res

AC77