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], ]
1 class Solution(object): 2 def combine(self, n, k): 3 """ 4 :type n: int 5 :type k: int 6 :rtype: List[List[int]] 7 """ 8 res = [] 9 nums = list(range(1, n+1)) 10 self.dfs(nums, k, 0, res, []) 11 12 return res 13 14 def dfs(self, nums, k, step, res, line): 15 if len(nums) < k - step: 16 return 17 if step == k: 18 res.append([x for x in line]) 19 20 for i, x in enumerate(nums): 21 line.append(nums[i]) 22 self.dfs(nums[i+1:], k, step + 1, res, line) 23 line.pop() 24
L15-L16 判段一下剩下的可以填的元素个数是不是比剩下的空位少，如果是的话可以提前结束这个branch的搜索。没有这两行的话，程序超时。
原文：http://www.cnblogs.com/lettuan/p/6148021.html