回溯算法
回溯算法其实就是我们常说的 DFS 算法,本质上就是⼀种暴⼒穷举算法。解决⼀个回溯问题,实际上就是⼀个决策树的遍历过程。你只需要思考3 个问题:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,⽆法再做选择的条件。
代码方面,回溯算法的框架:
result = []
def backtrack(路径, 选择列表):
if 满⾜结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
其核⼼就是 for 循环⾥⾯的递归,在递归调⽤之前「做选择」,在递归调⽤之后「撤销选择」,特别简单。
本文通过「全排列」和DFS过程来讲述上述回溯框架。
46. 全排列
解决方案:回溯算法
全排列的穷举过程可以构造决策树。全排列的计算就是决策树的遍历结果。
对于图中的红色节点所在状态::[2] 就是「路径」,记录你已经做过的选择;[1,3] 就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层,在这⾥就是选择列表为空的时候。这可以解答开头介绍的⼏个名词。
如果你理解这些术语,你可以使用“路径”和“选择”列表作为决策树上每个节点的属性,如下图列出了几个节点的属性:
我们定义的 backtrack 函数其实就像⼀个指针,在这棵树上游⾛,同时要正确维护每个节点的属性,每当⾛到树的底层,其「路径」就是⼀个全排列。
“路径”和“选择”是每个节点的属性。为了正确维护树上游节点的属性,函数需要在前序遍历(进入节点之前)和后序遍历(出节点)中执行一些动作:
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. 路径总和
解法: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