目录

0077:组合(★)

力扣第 77 题

题目

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

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

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

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

相似问题:

分析

除了直接调库,可以用回溯。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(i):
            if i>n or len(path)==k:
                if len(path)==k:
                    res.append(path[:])
                return
            dfs(i+1)
            path.append(i)
            dfs(i+1)
            path.pop()
        res,path = [],[]
        dfs(1)
        return res

198 ms