77. 组合

Lan
Lan
2023-10-12 / 0 评论 / 128 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2023年10月12日,已超过405天没有更新,若内容或图片失效,请留言反馈。

给定两个整数 n 和 k,返回范围 [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

# @Time    : 2023/10/12 16:43
# @Author  : Lan
# @File    : 77.组合.py
# @Software: PyCharm
"""
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
"""
from typing import List


class Solution:
    result = []
    temp = []

    def backtracking(self, n, k, start):
        if len(self.temp) == k:
            self.result.append(self.temp.copy())
        else:
            for i in range(start, n - (k - len(self.temp)) + 2):
                self.temp.append(i)
                self.backtracking(n, k, i + 1)
                self.temp.pop()

    def combine(self, n: int, k: int) -> List[List[int]]:
        self.result = []
        if n == k:
            return [[i for i in range(1, n + 1)]]
        self.backtracking(n, k, 1)
        return self.result


print(Solution().combine(4, 2))
0

评论 (0)

取消