77. 组合

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/combinations

题目

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

示例:

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

解题思路

思路：组合数

先审题，题目要求给定 n，返回 1…n 中所有可能的 k 个数组合。咱们能够发现，这其实就是高中数学概念上的组合数问题。

组合的定义： 从 n 个不同元素中，任取 m（$m \leq n$）个不同元素组成一组，称为组合。

组合数的定义： 从 n 个不同元素中，任取 m（$m \leq n$）个不同元素的所有组合的个数，叫做组合数，记为 $C_{n}^{m}$。

组合数有这样一个性质：

$$C_{n+1}^{m} = C_{n}^{m} + C_{n}^{m-1}$$

这里咱们令 n’ = n+1，那么下面的式子则会变成：

$$C_{n’}^{m} = C_{n’-1}^{m} + C_{n’-1}^{m-1}$$

其实也就等同于：

$$C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$$

这里咱们能够这样去了解下面的式子。假如当初从 n 个元素选 m 个元素，也就是 $C_{n}^{m}$。这里，咱们先抉择一个须要非凡思考的元素，那么就会有以下两种状况：

• 入选取的元素中不含这个非凡元素，那么就须要在残余的 n-1 个元素中选出 m 个元素，也就是 $C_{n-1}^{m}$；
• 入选取的元素中含有这个非凡元素，那么就须要从残余的 n-1 个元素中选出 m-1 个元素，也就是 $C_{n-1}^{m-1}$。

最终，将两种状况联合起来，从 n 个元素选 m 个元素的状况。

那么就依照这个思路，进行实现，这里每次选取非凡元素为可选元素汇合中最小的元素。

具体代码实现如下（递归办法）。

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        tmp = []

        def helper(special, n, k):
            # k 个元素抉择实现，增加到返回列表中
            if k == 0:
                # 这里留神增加的是正本
                # 具体起因，倡议自行调试查看
                ans.append(tmp[::])
                return
            # 示意残余元素不够抉择 k 个元素，间接返回
            if k > n:
                return

            tmp.append(special)
            helper(special+1, n-1, k-1)
            tmp.pop()
            helper(special+1, n-1, k)

        helper(1, n, k)

        return ans

# n = 4
# k = 2
# solution = Solution()
# ans = solution.combine(n, k)
# print(ans)

欢送关注

公众号【书所集录】