[数据结构与算法][Leetcode] 每日两题 46 112 -day98重温回溯算法（1）

重温回溯算法（1）

回溯算法的思路就是把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。本质上还是暴力枚举。使用的思想和DFS类似。

详细描述 ：

回溯法按深度优先策略搜索问题的解空间树。

首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。

如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。

46. 全排列

? 回溯思想，对于当前的一个list 暴力枚举 nums中的每个数 判断是否包含在内，若不在内则加入list，扩充后的list再次进行下一轮枚举，而返回条件就是list长度等于nums的长度，并且将该list保存。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        res = []
        def dfs(lis):
            if len(lis) ==len(nums):
                res.append(lis)
                return
            for i in nums:
                thi = lis.copy()
                if i not in thi: 
                    thi.append(i)
                    dfs(thi)
                
        dfs([])
        return res

112. 路径总和

https://blog.csdn.net/weixin_43146899/article/details/121862478

之前做过这道题 之前的方法就是BFS 类似二叉树的层序遍历， 那么这次重温回溯算法之后 用dfs来做 总体时间差不多。

唯一需要注意的是 本题是返回 True 或者False 所以每次回溯的时候都要返回当前的一个是否达到目标值情况

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        
        if not root:
            return False
        def dfs(node,num):
            if num == targetSum and not node.left and not node.right:
                return True
            l_flag, r_flag = False, False
            if node.left :
                l_flag = dfs(node.left,num+node.left.val)
            if node.right:
                r_flag = dfs(node.right,num+node.right.val)
            return l_flag or r_flag
        
        return dfs(root,root.val)