组合问题
组合问题
77.Combinations
会超时的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
- 如果 k==n ，则全选。
- n > k 又可以分成两类：
- 选了n， 则在余下的n-1中选k-1
- 没有选n， 则在余下的n-1中选k
注意一下会有两个base case，因为k在不断减小和n在不断减小，所以写起来可以这样：
def combine(n,k):
if k == 1:
return [[i+1] for i in range(n)]
if n == k:
return [range(1, k+1)]
# choose n , not choose n
return [r + [n] for r in combine(n-1,k-1)] + combine(n-1,k)
print combine(20,16)
39. Combination Sum
使用正常递归思路
40. Combination Sum II
重复做跳过处理
