题目

题目链接

题目原文 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

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

题目解析

本题就是经典的数学问题,求各种可能的组合,注意这里的组合不能重复,[1,4][4,1]是一种组合。

解题方法

投机取巧方法

因为,本人只刷python语言,对于python来说,有一个高效的标准库itertools,可以帮助我们进行两两组合,给出排列或者组合等等操作。

使用itertools的代码仅需一行,运行时间极短,因为它内部仍是用c编写。

from itertools import combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return [j for j in combinations([i for i in range(1,n+1)],k)]

DFS回溯

当然,既然要刷题,就要掌握点新知识,或者巩固已有知识。

要遍历解空间的所有结果,肯定可以用DFS进行遍历搜索,这里需要返回所有可能情况,当然要用到回溯的技巧。

我们先从n=4,k=2的例子,来解析遍历的过程。

解空间解空间

这里有两个细节:

  • 按顺序进行选择,以保证不会重复,例如,选择2后,在(3,4)中进行选择,而不考虑1。
  • 因为,我们只选择k个数,因此,可以判断当前已选择的个数与候选集个数的和,若小于k那么剪枝。

我们回顾一下DFS回溯算法的框架:

    def dfs(node):
        #终止条件
        if 终止条件:
            #记录某次结果
            result.append(path)
            return 
        #剪枝
        for 某节点 in 当前可选择节点:
            #剪枝
            path.append(某节点) #选择
            dfs(某节点)
            path.pop()#取消选择,回溯   

对于,本题在每次迭代时,需要维护当前可选择数,具体代码如下:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result=list()
        path=list()
        num_list=[i for i in range(1,n+1)]
        def dfs(cur_num,cur_index):
            #终止条件
            if len(path)==k:
                result.append(list(path))
                return
            #剪枝
            if len(num_list[cur_index:]) + len(path)<k:
                return 
            for i in num_list[cur_index:]:
                #进行选择
                path.append(i)
                dfs(i,i)
                path.pop()
                        
        dfs(0,0)
        return result