[Leetcode][python]Combinations/组合

墨蓝 2022-06-07 11:42 186阅读 0赞

## 题目大意 ##

求在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