LeetCode 刷题之回溯算法

柔情只为你懂 2023-09-29 19:23 15阅读 0赞

## 1. 回溯算法框架套路 ##

回溯可以理解是暴力递归 + 剪枝，**解决一个回溯问题，实际上就是一个决策树的遍历过程**，大致需要分为以下三步

*  路径：已作出的选择
 *  选择列表：即当前可以做的选择
 *  结束条件：即达到决策树底层，无法再做选择的条件

result = []
    def backtrack(路径, 选择列表):
        if 满足结束条件:
            result.add(路径)
            return
    
        for 选择 in 选择列表:
            做选择
            backtrack(路径, 选择列表)
            撤销选择

> 参考：[回溯算法详解（修订版）][Link 1]

## 2. 全排列 ##

[46. 全排列][46.]

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    
    示例 1：
    
    输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    示例 2：
    
    输入：nums = [0,1]
    输出：[[0,1],[1,0]]
    示例 3：
    
    输入：nums = [1]
    输出：[[1]]
     
    提示：
    
    1 <= nums.length <= 6
    -10 <= nums[i] <= 10
    nums 中的所有整数 互不相同

题解：

class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            res = []
            track = []
            self.backtrack(res, track, nums)
            return res
    
        def backtrack(self, res, track, nums):
            # bad case
            if len(track) == len(nums):
                res.append(track[:])
                return
    
            for i in range(0, len(nums)):
                if nums[i] in track:
                    continue 
    
                track.append(nums[i])
                self.backtrack(res, track, nums)
                track.pop() # 撤销条件

## 3. 子集 ##

[78. 子集][78.]

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    
    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
    
    示例 1：
    
    输入：nums = [1,2,3]
    输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    示例 2：
    
    输入：nums = [0]
    输出：[[],[0]]
     
    
    提示：
    
    1 <= nums.length <= 10
    -10 <= nums[i] <= 10
    nums 中的所有元素 互不相同

题解：

class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            res = []
            track = []
            self.backtrack(res, nums, track, 0)
            return res
    
        def backtrack(self, res, nums, track, start):
            """
            start: 控制树枝的生长避免产生重复的子集
            track：记录根节点到每个节点的路径的值
            [] 也是它的子集
            """
            res.append(track[:])
    
            # base case
            if start == len(nums):
                return
    
            for i in range(start, len(nums)):
                track.append(nums[i])
                self.backtrack(res, nums, track, i + 1)
                track.pop()

> 参考：[一文秒杀排列组合问题的 9 种题型][9]

## 4. 括号生成 ##

[22. 括号生成][22.]

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    
    示例 1：
    
    输入：n = 3
    输出：["((()))","(()())","(())()","()(())","()()()"]
    示例 2：
    
    输入：n = 1
    输出：["()"]
     
    提示：
    
    1 <= n <= 8

题解：

class Solution:
        def generateParenthesis(self, n: int) -> List[str]:
            result = []
            self.backtracking(n, result, 0, 0, "")
            return result
    
        def backtracking(self, n, result, left, right, s):
            # 右括号数目大于左括号数目就不符合有效括号组合
            if right > left:
                return
            
            if left == n and right == n:
                result.append(s)
                return
    
            # 先加左括号
            if left < n:
                self.backtracking(n, result, left+1, right, s + "(")
    
            # 右边的括号小于左边的括号，加右边的括号
            if right < left:
                self.backtracking(n, result, left, right+1, s + ")")

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&scene=21#wechat_redirect
[46.]: https://leetcode.cn/problems/permutations/
[78.]: https://leetcode.cn/problems/subsets/
[9]: https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247496080&idx=1&sn=a2ae8c8ebf13c7ea704ffb6b16018f08&scene=21#wechat_redirect
[22.]: https://leetcode.cn/problems/generate-parentheses/