LeetCode 77. Combinations 20170530补上周

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

 题目大意：给定两个整数n和k，返回所有包含k个从1到n中的数的集合

 解题思路：可以用回溯法结合递归，先遍历1到n抽取一个数i，然后下一次递归时每种情况都要从i+1开始选数，因为为了避免出现重复的情况，所以每次选取的数都要比上一次选取的数大。递归的截止条件是当抽取的数量达到k为止。但是一直出错，报错结果为超时，百思不得其解。后来想了想，假如k是7，一开始就抽了一个比较大的数，比如说n-2，那么比n-2大的数只有两个，而接下来还需要抽6个数，所以这种情况就铁定无法满足条件的，就可以提前终止这种情况的下一步递归了，这样能够大大减小复杂度。图1为超时代码，图2为成功代码。

class Solution(object):
　　def combine(self, n, k):
　　　　"""
　　　　:type n: int
　　　　:type k: int
　　　　:rtype: List[List[int]]
　　　　"""
　　　　A = []
　　　　count = 0
　　　　def backtracking(start, count, List):
　　　　　　if count == k:
　　　　　　　　A.append(List)
　　　　　　　　return
　　　　　　if n - start + 1 < k - count:
　　　　　　　　return
　　　　　　for i in range(start, n + 1):
　　　　　　　　backtracking(i + 1, count + 1, List + [i])
　　　　if k == 0 or n == 0:
　　　　　　return
　　　　else:
　　　　　　backtracking(1, 0, [])
　　　　　　return A