Leetcode题77、组合（Python题解）微软面试题

问题：

题目来源：力扣（LeetCode）

leetcode77.组合

难度：中等

分析： 回溯法。 组合和排列的差别在于，组合是无序的，因此[1,2], [2,1]对于排序是不同的元素，但对于组合来说他们是相同的。 因此在回溯的时候，我们需要避免这种情况。避免的方法是，在选择第一个位置的值后，第二个位置的值应该向备选数组中的后面选择，永远不向第一个元素之前选择，这样保证了组合中的数字全部都是正序，不存在倒序，不会产生重复。正序就可以包括所有的组合，因此也没有遗漏。

题解中没有记录回溯层数，因为回溯终止条件可以通过组合长度来判定，因此回溯层数不记录也可以。

这道题也可以用python技巧来做 解决方法： 1：回溯法

#回溯法 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: if n == 0 or k == 0: return [] def backtrace(index): if len(path) == k: res.append(path[:]) #浅拷贝，这一步很重要 for i in range(index,n): #这里，向后选择 path.append(nums[i]) backtrace(i+1) #向下回溯，这里回溯传递的是向后选择的索引位置。 path.pop() #先生成数 nums = [i for i in range(1,n+1)] path = [] res = [] backtrace(0) return res

2：python技巧

#python技巧 #Python itertools模块combinations(iterable, r)方法可以创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序。 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: return list(itertools.combinations(range(1,n+1),k))