77-组合

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

---

示例

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

---

解法1

核心思想：使用库函数combinations，直接生成。

from itertools import combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(combinations(range(1,n+1),k))

解法2

核心思想：利用回溯算法，每到列表中的长度=k时，添加到res一次

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        def backtrack(i, k, tem):
            if k == 0:
                res.append(tem)
                return
            for j in range(i, n+1):
                backtrack(j + 1, k - 1, tem+[j])

        backtrack(1, k, [])
        return res

---

相关信息

LeetCode：Discussion | Solution