题目描述

给定两个整数 n 和 k. 返回从 1, 2, ... , n 中选出 k 个数的所有可能的组合。

你可以以任意顺序返回所有的组合, 但是一个组合内的所有数字需要是升序排列的.

测试样例

输入: n = 4, k = 2

输入: n = 4, k = 1

输出: [[1],[2],[3],[4]]

解题思路

典型地用DFS来解决。

设置一个全局列表result来存储所有组合，以及一个临时列表tmp来存储每一种组合。

每次DFS往tmp中加入一个数字后，使k减1，代表还剩几个数需要加入tmp中。

每次DFS时，若k为0，代表已经满足要求，将tmp拷贝一份添加到result中。

另外，由于每种组合需要有k个数，于是可以小优化下，若取出一个数字i后，剩余 i+1, i+2, ..., n已经不足 k-1 个，那么这种组合是不满足要求的，因此取数字的边界可以设置为 n-k+1。

代码

class Solution:

    """

    @param n: Given the range of numbers

    @param k: Given the numbers of combinations

    @return: All the combinations of k numbers out of 1..n

    """

    def combine(self, n, k):

        if not k:

            return [[]]

        if k == 1:

            return [[num] for num in range(1, n + 1)]

        result = []

        # 第一个数字从1开始

        self.dfs(1, n + 1, k, [], result)

        return result

    def dfs(self, index, n, k, tmp, result):

        if not k:

            # 注意这里tmp需要拷贝

            result.append(tmp[:])

            return

        # 每次取出一个数字，与后面的k-1个数字组合

        for i in range(index, n - k + 1):

            tmp.append(i)

            # 每次加入一个数字后k减1，代表还剩多少个数需要加入组合

            self.dfs(i + 1, n, k - 1, tmp, result)

            tmp.pop()