077 combinations
77. Combinations
题目： https://leetcode.com/problems/combinations/
难度 : Medium
思路一： python作弊法
import itertools
p = [4, 8, 15, 16, 23, 42]
c = itertools.combinations(p, 4)
for i in c:
print i
结果：
(4, 8, 15, 16)
(4, 8, 15, 23)
(4, 8, 15, 42)
(4, 8, 16, 23)
(4, 8, 16, 42)
(4, 8, 23, 42)
(4, 15, 16, 23)
(4, 15, 16, 42)
(4, 15, 23, 42)
(4, 16, 23, 42)
(8, 15, 16, 23)
(8, 15, 16, 42)
(8, 15, 23, 42)
(8, 16, 23, 42)
(15, 16, 23, 42)
作弊AC代码:
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
import itertools
return [list(i) for i in itertools.combinations(range(1,n+1), k)]
思路二：
标准的recursion
但是会超时
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
ans = []
self.dfs(n, k, 1, [], ans)
return ans
def dfs(self, n, k ,start, lst, ans):
if k == 0 :
ans.append(lst)
return
for i in range(start, n+1):
self.dfs(n, k - 1, i + 1,lst +[i], ans)
理解方式
1 2 3
12 13 14 23 24 34
可以参照这里
解法三：
采用递归的方式，在n个数中选k个，如果n大于k，那么可以分类讨论，如果选了n，那么就是在1到(n-1)中选(k-1)个，否则就是在1到(n-1)中选k个。递归终止的条件是k为1，这时候1到n都符合要求。
注意一开始这里的else part花了我一点时间来理解，因为n必定大于k，所以这样递归当 n == k的时候选法就是code原作者的写法，也就是直接[range(1,k+1)]
参考这里： https://shenjie1993.gitbooks.io/leetcode-python/content/077%20Combinations.html
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
if k == 1:
return [[i + 1] for i in range(n)]
result = []
if n > k:
result = [r + [n] for r in self.combine(n - 1, k - 1)] + self.combine(n - 1, k)
else: #n == k
# result = [r + [n] for r in self.combine(n - 1, k - 1)]
result = [range(1,k+1)]
return result
