首页 > 代码库 > Leetcode 77, Combinations
Leetcode 77, Combinations
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的搜索。没有这两行的话,程序超时。
Leetcode 77, Combinations
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。