【LeetCode】46 and 112(回溯算法)

回溯算法

回溯算法其实就是我们常说的 DFS 算法,本质上就是⼀种暴⼒穷举算法。解决⼀个回溯问题,实际上就是⼀个决策树的遍历过程。你只需要思考3 个问题:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,⽆法再做选择的条件。
代码方面,回溯算法的框架:

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

其核⼼就是 for 循环⾥⾯的递归,在递归调⽤之前「做选择」,在递归调⽤之后「撤销选择」,特别简单。
本文通过「全排列」和DFS过程来讲述上述回溯框架。

46. 全排列

【LeetCode】46 and 112(回溯算法)
解决方案:回溯算法
全排列的穷举过程可以构造决策树。全排列的计算就是决策树的遍历结果。
【LeetCode】46 and 112(回溯算法)
对于图中的红色节点所在状态::[2] 就是「路径」,记录你已经做过的选择;[1,3] 就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层,在这⾥就是选择列表为空的时候。这可以解答开头介绍的⼏个名词。
如果你理解这些术语,你可以使用“路径”和“选择”列表作为决策树上每个节点的属性,如下图列出了几个节点的属性:
【LeetCode】46 and 112(回溯算法)
我们定义的 backtrack 函数其实就像⼀个指针,在这棵树上游⾛,同时要正确维护每个节点的属性,每当⾛到树的底层,其「路径」就是⼀个全排列。
“路径”和“选择”是每个节点的属性。为了正确维护树上游节点的属性,函数需要在前序遍历(进入节点之前)和后序遍历(出节点)中执行一些动作:
【LeetCode】46 and 112(回溯算法)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        subsets = []
        def dfs(nums, subset, used):
        	# 结束条件:子集长度等于原数组长度,表示一个排列
            if len(subset) == len(nums):
                temp = list(map(lambda x: nums[x], subset))
                # if temp not in subsets:
                subsets.append(temp)
                return 
            # 遍历所有选择
            for i in range(len(nums)):
            	# 未被选择
                if used[i] == 0:
                	# 做选择
                    subset.append(i)
                    used[i] = 1
                    dfs(nums, subset, used)
                    # 撤销选择
                    subset.pop()
                    used[i] = 0
        used = [0] * len(nums)
        dfs(nums, [], used)
        return subsets

112. 路径总和

【LeetCode】46 and 112(回溯算法)
【LeetCode】46 and 112(回溯算法)
解法:DFS,回溯算法
DFS其实就是一种回溯算法,本质上就是⼀种暴⼒穷举算法。对于该题,我们用DFS算法对每条路径的和进行计算,并判断其是否和目标值相等。

# 为了便于理解回溯框架的使用,我们在代码中详细列出了做选择的过程。
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # sumValue = 0
        if not root:
            return False
        def dfs(root, value):
            # nonlocal sumValue
            if not root:
                return False
            # 结束条件
            if not root.left and not root.right:
                return value == targetSum
            # 当前节点的选择列表为 left 和 right 中非空节点。
            # 下面代码显示遍历所有选择
            if root.left:
            	# 做出选择
                value += root.left.val
                left = dfs(root.left, value)
                # 撤销选择
                value -= root.left.val
            else:
                left = False
            if root.right:
            	# 做出选择
                value += root.right.val
                right = dfs(root.right, value)
                # 撤销选择
                value -= root.right.val
            else:
                right = False
            return left or right
        return dfs(root, root.val)

版权声明:本文为博主每天学一点吧原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/m0_64204369/article/details/123173659

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2022年3月1日 下午7:55
下一篇 2022年3月1日 下午8:09

相关推荐