77. 组合
给定两个整数
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
通过次数208,919提交次数271,240
法1 回溯
思路
剪枝，通过元素个数限制来剪纸
题解
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: self.res = [] self.backtrack(path=[], start=1, n=n, k=k) return self.res def backtrack(self, path, start, n, k): if len(path)==k: self.res.append(path[:]) return for i in range(start, n+1): if n+1-i < k-len(path): return path.append(i) self.backtrack(path, i+1, n, k) path.pop()