您现在的位置是：首页 > Python

当前栏目

[Leetcode][python]Combinations/组合

递归

2023-03-02 11:48:18 时间

## 题目大意 ##

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

## 解题思路 ##

DFS(回溯法)

## 代码 ##

### DFS ###

和排列蛮像的，只不过到了k个数就停止递归了

class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            def dfs(start, valuelist):
                if self.count == k: 
                    ret.append(valuelist)
                    return
                for i in range(start, n + 1):
                    self.count += 1
                    dfs(i + 1, valuelist + [i])
                    self.count -= 1
    
            ret = []
            self.count = 0
            dfs(1, [])
            return ret

### 直接用数字做 ###

看图，摆明了不让我们这么做么，这最后一个数据集坑死了多少人。  
![这里写图片描述][SouthEast]

class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            self.result = []
            temp = []
            self.combineHelper(n, k, 0, 1, temp)
            return self.result
    
        def combineHelper(self, n, k, length, num_now, temp):
            # print 'start', temp, list_num, length, self.k
            if length == k:
                # print 'add', temp
                self.result.append(temp[:])  # 这里直接写temp，就会导致result内的temp永远是一个实例，后面修改temp会使得result一直在变化
                # print 'result', self.result
                return
            for i in range(num_now, n+1):
                temp.append(i)
                self.combineHelper(n, k, length+1, i+1, temp)
                temp.pop()

### 转为list做 ###

**最后一个测试集TLE**

class Solution(object):
        def combine(self, n, k):
            """
            :type n: int
            :type k: int
            :rtype: List[List[int]]
            """
            self.k = k
            self.result = []
            list_num = [i for i in range(1, n+1)]
            self.combineHelper(0, [], list_num)
            return self.result
    
        def combineHelper(self, length, temp, list_num):
            # print 'start', temp, list_num, length, self.k
            if length == self.k:
                # print 'add', temp
                self.result.append(temp[:])  # 这里直接写temp，就会导致result内的temp永远是一个实例，后面修改temp会使得result一直在变化
                # print 'result', self.result
                return
            for i, num in enumerate(list_num):
                temp.append(num)
                # print temp, list_num[i+1:]
                # print '-------'
                self.combineHelper(length+1, temp, list_num[i+1:])
                temp.pop()

## 总结 ##

做DFS时，有很多小细节，比如该题，temp需要pop，不能在上面加入result那里做，应该是在调用递归后做。  
此题肯定有非递归写法，有空琢磨。

[SouthEast]: /images/20220607/4ede99b3402241ec9f9352164e4abba7.png

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

[Leetcode][python]Combinations/组合

相关文章