组合数

概述

给出n和k，求 C(n, k)对应的所有组合
例如：n=4, k=2
返回：[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

原题

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路

combine(n, k) 所有可能的组合分两部分，包含n和不包含n。其中：

• 不包含n的结果与combine(n-1, k) 相同
• 包含n的结果相当于把combine(n-1, k-1)的每一种组合中再加一个n

例如：
求combine(4, 2)

• 包含n：combine(3, 1)结果为[[1], [2], [3]]，每个结果加上4，得到[[1, 4], [2, 4], [3, 4]]
• 不包含n：combine(3, 2)结果为[[1, 2], [1, 3], [2, 3]]

合并，得到combine(4, 2)的结果[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

代码

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if n == k:
            return [list(range(1, n+1))]
        if k == 0:
            return []
        if k == 1:
            return [[i] for i in range(1, n+1)]
        part1 = self.combine(n-1, k-1)
        part2 = self.combine(n-1, k)
        part1 = [i + [n] for i in part1]
        return part1 + part2