77. Combinations

求在1到n个数中挑选k个数的所有的组合类型

思路：采用递归的方式，在n个数中选k个，如果n大于k，那么可以分类讨论，如果选了n，那么就是在1到(n-1)中选(k-1)个，否则就是在1到(n-1)中选k个。递归终止的条件是k为1，这时候1到n都符合要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        # 6 star, 起初用dfs做的，结果一直超时，
        # todo, 这个解法是别处看来的，需要自己再做
        if k > n:
            return []
        if k == 1:
            return [[i + 1] for i in range(n)]
        if n > k:
            result = [r + [n] for r in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)  # 有n的 和 没n的
        else:
            result = [r + [n] for r in self.combine(n - 1, k - 1)]  # 之所以有这个else, 是处理n=k的
        return result