组合

Leetcode Link: 77. 组合 - 力扣（LeetCode）

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

组合，是不考虑顺序的，即[1, 2]和[2, 1]是一样的

解法一

思路：自己的思路 每次回溯的时候都给出一个choose。

题解：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(choose):
            nonlocal k, path, res
            # 返回条件
            if len(path) == k:
                # 这里必需使用deepcopy
                res.append(copy.deepcopy(path))
                return
 
            for idx, val in enumerate(choose):
                path.append(val)
                backtracking(choose[idx+1:])
                path.pop()
        
        res = [] # 这里不可使用 res = path = []，会导致两者同时变化
        path = []
        choose = [x for x in range(1,  n+1)]
        backtracking(choose)
        return res

考虑剪枝，当当前的path和剩余的选择加起来也不够k个元素的时候，后面就不用看了

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(choose):
            nonlocal k, path, res
            # 返回条件
            if len(path) == k:
                # 这里必需使用deepcopy
                res.append(copy.deepcopy(path))
                return
 
            for idx, val in enumerate(choose):
                path.append(val)
                # 剪枝, 不能放在 for 的第一句，会丢val元素
                if len(path) + len(choose[idx+1:]) < k:
                    path.pop() # 必需记得po出来
                    return 
                backtracking(choose[idx+1:])
                path.pop()
        
        res = [] # 这里不可使用 res = path = []，会导致两者同时变化
        path = []
        choose = [x for x in range(1,  n+1)]
        backtracking(choose)
        return res

解法二

思路：其他人的解法，不用每次都给出一个choose，直接给一个索引，然后在 nonlocal 的数组中直接确定choose区间

题解：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        def backtrack(n, k, StartIndex):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(StartIndex, n + 1):
                path.append(i)
                backtrack(n, k, i+1)
                path.pop()
        backtrack(n, k, 1)
        return res

启发和联系