LeetCode Problem 77-Combinations

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

示例:

1 2 3 4 5 6 7 8 9 10

输入: 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 11

class Solution: def combine(self, n: int, k: int) -> List[List[int]]: def backtrack(first=1, tmp=[]): if len(tmp) == k: rs.append(tmp) return for i in range(first, n + 1): backtrack(i + 1, tmp + [i]) rs = [] backtrack() return rs

相似问题

1. Combination Sum
2. Permutations