题目: 组合

组合

难度：中等

给定两个整数 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

分析

方法一：回溯法

使用回溯法是一种很自然的解决组合问题的方法。其基本思路是从第一个数字开始，依次选取每个数字，如果已经选取了k个数字，就记录下来这个组合。在选取下一个数字之前，将前面选取的数字回溯（撤销）掉，然后选择下一个数字。

以下是使用回溯法解决LeetCode的组合问题的Python代码：

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

方法二：递归法

使用递归法解决组合问题的方法和回溯法类似。其基本思路是，每次从n个数中选取一个数，然后再从剩下的n-1个数中选取k-1个数。当k等于1时，递归结束。

以下是使用递归法解决LeetCode的组合问题的Python代码：

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

方法三：迭代法

使用迭代法解决组合问题也是一种常见的方法。其基本思路是，从1到n中选取k个数，可以将其转换为从1到n-k+1中选取1个数，从1到n-k+2中选取1个数……从1到n中选取1个数的问题。因此，可以通过迭代的方式依次求解。

以下是使用迭代法解决LeetCode的组合问题的Python代码：

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