[Leetcode][python]Combinations/组合
[Leetcode][python]Combinations/组合
蛮三刀酱
发布于 2019-03-26 16:22:23
发布于 2019-03-26 16:22:23
题目大意
求在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直接用数字做
看图，摆明了不让我们这么做么，这最后一个数据集坑死了多少人。
这里写图片描述
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那里做，应该是在调用递归后做。 此题肯定有非递归写法，有空琢磨。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月20日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录