代码随想录算法训练营第二十四天| LeetCode77. 组合

一、回溯算法

有递归就有回溯，回溯通常都在递归函数的下方，可看视频：回溯算法

回溯算法三部曲：

        1：确定递归函数的参数和返回值

        2：确定终止条件

        3：单层递归逻辑

二、LeetCode77. 组合

        1：题目描述（77. 组合）

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

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

        2：解题思路（视频详解）

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []       # 存放所有符合要求的组合结果
        path = []      # 存放每个符合要求的组合
        # 确认递归函数的参数和返回值
        def pathcombine(n, k, startsize):
            # n表示范围[1,n]的n
            # k表示k个数的组合
            # startsize表示每个组合的开始位置
 
            # 确定终止条件
            if len(path) == k:
                # 当path的大小等于k的时候，表示此时的path中的组合满足了题意
                # 就需要将path加入到res中
                res.append(path[:])
                # 加入后，然后返回上一层
                return
            # 单层递归逻辑
            for i in range(startsize, n+1):
                # 每层递归，i都是从startsize开始，到n+1结束，因为range()函数，左闭右开
                path.append(i)
                # 进入递归,下一层递归函数的开始位置是从当前位置的下一个位置开始
                # 所以startsize是i+1
                pathcombine(n, k, i+1)
                # 回溯，符合条件后，需要把加进来的元素pop出去
                path.pop()
        pathcombine(n, k, 1)
        return res

        进行优化：剪枝

假如n=4，k=3，那么组合就是[1,2,3],[1,3,4],[2,3,4]；我们就不需要再从3开始遍历进行取值，因为就算取了值，最后的长度也不符合要求，所以进行一个剪枝操作

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []       # 存放所有符合要求的组合结果
        path = []      # 存放每个符合要求的组合
        # 确认递归函数的参数和返回值
        def pathcombine(n, k, startsize):
            # 确定终止条件
            if len(path) == k:
                # 当path的大小等于k的时候，表示此时的path中的组合满足了题意
                # 就需要将path加入到res中
                res.append(path[:])
                return
            # 单层递归逻辑
            # 剪枝就是修改i的取值范围，可以将n+1修改为：n-(k-len(path))+1
            size = n-(k-len(path))+1         # k-len(path)表示还剩几个需要取
            for i in range(startsize, size+1):
                # 每层递归，i都是从startsize开始，到size+1结束，因为range()函数，左闭右开
                path.append(i)
                # 进入递归,下一层递归函数的开始位置是从当前位置的下一个位置开始
                # 所以startsize是i+1
                pathcombine(n, k, i+1)
                # 回溯，符合条件后，需要把加进来的元素pop出去
                path.pop()
        pathcombine(n, k, 1)
        return res