跳到主要内容

77. 组合(Medium)

题目描述​

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

样例​

Input: n = 4, k = 2
Output:
[[1, 2], 
 [1, 3], 
 [1, 4],
 [2, 3], 
 [2, 4],
 [3, 4]]

题目解析​

详细可以参考 回溯算法：求组合问题！

Python示例​

def backtracking(n, k, ans, startIndex, tmp):
    if len(tmp) == k:
        ans.append(tmp[:])
        return 
    for i in range(startIndex, n + 1):
        tmp.append(i)
        backtracking(n, k, ans, i + 1, tmp)  # i + 1 可以避免重复
        tmp.pop()
    
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        backtracking(n, k, ans, 1, [])
        return ans