组合问题
组合问题
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
重复做跳过处理

