组合

# 组合

# 77. 组合 (opens new window)

难度：中等

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

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

示例 1：

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

1
2
3
4
5
6
7
8
9
10

示例 2：

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

1
2

提示：

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

n, k = map(int, input().strip().split())
res = []
path = []


def dfs(n, k, start_index, res):
    global path
    if n - start_index + 1 < k - len(path):
        return
    if len(path) == k:
        res.append(path.copy())
        return

    for i in range(start_index, n + 1):
        path.append(i)
        dfs(n, k, i + 1, res)
        path.pop()


dfs(n, k, 1, res)
print(res)

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

编辑

← BFS层序遍历全排列→