网站域没到期不能续费吗,百度企业查询,柳州房地产网站建设,现在的建筑模板一般用什么回溯核心思想
回溯算法的关键在于#xff1a;不合适就退回到上一步具体的#xff1a;通过枚举法#xff0c;对所有可能性进行遍历#xff0c;枚举顺序是一条路走到黑#xff0c;走到头满足条件后#xff0c;退一步#xff0c;再尝试之前没走过的路#xff0c;直到所有…回溯核心思想
回溯算法的关键在于不合适就退回到上一步具体的通过枚举法对所有可能性进行遍历枚举顺序是一条路走到黑走到头满足条件后退一步再尝试之前没走过的路直到所有路都走了。
回溯关键点
一条路走到黑回退一步另寻他路
实现 for循环 另寻他路用for循环实现一个路径选择器逐个选择当前节点下的所有可能往下走的分支路径例如走到节点a向下有i条路用for循环将这i条路逐个尝试一遍。进入每条路后递归重复这个过程 递归 一条路走到黑把递归放在for循环内部那么for每次循环都在给出一个路径之后进入递归也就是继续向下走了回退一步直到递归出口无路可走为止那么从递归出口出来就会实现回退一步。 for循环与递归配合就可以实现回溯 当递归从递归出口出来后上一层的for循环就会继续执行而for循环继续执行就是给出了当前节点的下一条可行路径而后递归调用顺着这条从未走过的路径又向下走一步这就是回溯
def backtracking():# 定义回溯点if 回溯点: # 这条路走到底了保存该结果returnelse:# 逐步选择当前节点下的所有可能路径for route in all_route_set: if 剪枝条件: # 发现当前路不行剪枝前的操作return # 不继续往下走了退回上层换条路走else: # 当前路径可行保存当前数据 # 向下走之前要记住已经走过了这个节点。保存调用递归self.backtracking(xx) # 递归发生继续向下走回溯清理 # 该节点下的路径都走完了 剪枝 对于某些问题走着走着发现这条路不通再走也是浪费时间和内存所以直接退回去切掉这条路
39. 组合总数
39. 组合总和
一、题目难度
中等
二、相关标签与相关企业
[相关标签] [相关企业]
三、题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target找出 candidates 中可以使数字和为目标数 target 的所有不同组合并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于150个。
四、示例
示例1
输入
candidates [2, 3, 6, 7]
target 7输出
[[2, 2, 3], [7]]解释 2和3可以形成一组候选2 2 3 7。注意2可以使用多次。 7也是一个候选7 7。 仅有这两种组合。
示例2
输入
candidates [2, 3, 5]
target 8输出
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]示例3
输入
candidates [2]
target 1输出
[]五、提示
1 candidates.length 302 candidates[i] 40candidates 的所有元素互不相同1 target 40
思路
解空间
由输入无重复元素的整数数组candidates[xxxx]和目标整数target寻找使数字和为目标数的所有不同组合pathresult同一个数字candidates[i]可以被无限制重复选取
定义回溯函数参数与终止条件
参数 输入无重复元素的整数数组candidates[xxxx]和目标整数target可行结果path最终结果result当前节点start 核心思想 不断尝试当前节点可能的路径将当前节点可走的路径都尝试后向后移动start 更新节点位置。这里不涉及回溯回溯的含义是找到了一条path后把当前的path末尾的值吐出来相当于往后退一步再尝试其他的。所以这道题回溯点就是“找到了一条路”当前path满足sum(path) target。实际代码实现可能涉及直接动target不一定非这样写涉及剪枝比如某条路才走了一点就发现此路不通某两个节点相加后直接大于了target那么就没有必要继续走这条路了直接去掉这个值
具体代码实现步骤
再看回溯算法模板一步步根据这道题背景把代码步骤填进去
def backtracking():# 定义回溯点if 回溯点: # 这条路走到底了保存该结果returnelse:# 逐步选择当前节点下的所有可能路径for route in all_route_set: if 剪枝条件: # 发现当前路不行剪枝前的操作return # 不继续往下走了退回上层换条路走else: # 当前路径可行保存当前数据 # 向下走之前要记住已经走过了这个节点。保存调用递归self.backtracking(xx) # 递归发生继续向下走回溯清理 # 该节点下的路径都走完了 本题基本机制target target - candidates[i] 不断递归回溯检查targettarget 0走到头得到一条path放入result后回溯即删掉path最后一个值target 0: 剪枝 特解空集candidates则无结果return []初始化回溯函数的参数 输入无重复元素的整数数组candidates[xxxx]和目标整数target可行结果path []最终结果result []当前节点start 0将candidates[i]按照从小到大排列好:candidates.sort() 回溯函数 先定义回溯点
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:if len(candidates) 0:return []candidates.sort()path []res []重点在python中如果传参是mutable var, 那么传参相当于引用因此调用后如果调用函数的内部对该传入变量进行修改就会导致直接改变原始对象。这就是典型的privacy leak发生了。例如在这个list就是该mutable var而如果以path或res 为传参放在__DFS 中 那么就相当于在__DFS内部实际上用的都是一个物理地址下的res和path类似于全局变量。因此combinationSum下的局部变量path和res也在——DFS运行的过程中发生了改变。利用这个性质我们可以把mutable var当成传入参数从而实现全局变量的效果。self.__DFS(candidates, target, 0, path, res)return resDFS的实现def __DFS(self, candidates, target, begin, path, res):path path.copy()# 递归出口 就是余数为0if target 0:res.append(path) #记录该符合条件的结果return#若当前路径有可能可行。for i in range(begin, len(candidates)): # 我们现在到begin的节点上了if target - candidates[i] 0: # 剪枝条件return # 如果当前节点就不行了就不用继续了,这里到不用继续了即包括该depth不用继续了也包括该节点更大到child也不用继续了该节点pop出来path.append(candidates[i]) #记录当前为止self.__DFS(candidates, target - candidates[i], i, path, res)# 向下继续走记住递归不是return递归到实现是调用一旦return发生递归停止。path.pop() # 回朔清理。当前节点下的所有情况都进行完了该节点也不应该在path里面了。class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:主函数用于调用深度优先搜索DFS回溯来解决组合问题并且返回最终结果:param candidates: 无重复元素的整数数组从中选取数字组成满足条件target的组合:param target: 目标整数要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表每个组合都是一个整数列表# 特解candidates空集if len(candidates) 0: # 写成 not candidates 可以么return []# 对候选数组candidates进行预先排序方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path [] # 记录当前正在生成的一种数字组合情况初始是空列表result [] # 存储最终所有满足条件的数字组合初始是空列表# 调用DFS开始回溯过程self.__DFS(candidates, target, 0, path, result)return result# 双下划线约定为“私有”方法表示类的外部代码不应该直接调用这个函数def __DFS(self, condidates: List[int], target: int, begin: int, path: List[int], result: List[List[int]]):深度优先搜索DFS函数用DFS实现回溯算法找出满足条件的数字组合# 先对path(上次递归得到的一条路)进行拷贝# 避免后续操作中直接修改传入的path对象# 因为python中列表是可变对象传参时可能出现意外修改情况path path.copy()# 设置递归出口当目标值target0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target 0:result.append(path) # 存储path到resultreturn # 回到上个节点# 遍历从begin位置开始的condidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝如果当前值特别大走到这个值的时候直接超过了target# 即target - candidates[i] 0# 此路不通returnif target - candidates[i] 0:return # 否则将当前数值candidates[i]添加到path记录正在尝试的组合情况path.append(candidates[i])# 添加后相当于走到了下一个岔路口# 此时调用递归继续向下一层搜索 # path和result保持不变# 关键点在于更新目标值为target-candidates[i]表示剩余还需要凑的目标值# 本题更关键的更新begin为i# 因为candidates[i]可以被重复选择所以暂时不要跳到下一个i1self.__DFS(candidates, target - candidates[i], i, path, res)# 当下一层递归返回后说明当前节点下的所有可重复选# 可能情况都已经探索完成# 将path的最后一个元素弹出恢复到添加该元素之前的状态# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()
————————————————————————————————————————————
执行出错
AttributeError: Solution object has no attribute _Solution__DFS^^^^^^^^^^self.__DFS(candidates, target, 0, path, result)
Line 22 in combinationSum (Solution.py)^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ret Solution().combinationSum(param_1, param_2)
Line 105 in _driver (Solution.py)_driver()
Line 120 in module (Solution.py)
这里的错误主要在于内部方法 __DFS 的定义位置和调用方式。
错误分析
在Python中当你在类的方法内部定义另一个方法时这样的内部方法不能像你代码中那样直接在类的其他方法中调用。你把 __DFS 方法定义在了 combinationSum 方法内部这导致在 combinationSum 尝试调用 __DFS 时Python无法正确识别这个方法从而报出 Solution object has no attribute _Solution__DFS 的错误意思是 Solution 类的实例没有名为 _Solution__DFS 的属性方法在Python中也被视为属性。
修正建议
要解决这个问题你需要把 __DFS 方法定义在和 combinationSum 方法平级的位置也就是都作为 Solution 类的直接方法如下所示
from typing import Listclass Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:主函数用于调用深度优先搜索DFS回溯来解决组合问题并且返回最终结果:param candidates: 无重复元素的整数数组从中选取数字组成满足条件target的组合:param target: 目标整数要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表每个组合都是一个整数列表# 特解candidates空集if len(candidates) 0: # 写成 not candidates 可以么 可以的not candidates在candidates为空列表时会返回True效果相同return []# 对候选数组candidates进行预先排序方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path [] # 记录当前正在生成的一种数字组合情况初始是空列表result [] # 存储最终所有满足条件的数字组合初始是空列表# 调用DFS开始回溯过程self.__DFS(candidates, target, 0, path, result)return resultdef __DFS(self, candidates: List[int], target: int, begin: int, path: List[int], result: List[List[int]]):深度优先搜索DFS函数用DFS实现回溯算法找出满足条件的数字组合# 先对path(上次递归得到的一条路)进行拷贝# 避免后续操作中直接修改传入的path对象# 因为python中列表是可变对象传参时可能出现意外修改情况path path.copy()# 设置递归出口当目标值target0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target 0:result.append(path) # 存储path到resultreturn # 回到上个节点# 遍历从begin位置开始的candidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝如果当前值特别大走到这个值的时候直接超过了target# 即target - candidates[i] 0# 此路不通returnif target - candidates[i] 0:return# 否则将当前数值candidates[i]添加到path记录正在尝试的组合情况path.append(candidates[i])# 添加后相当于走到了下一个岔路口# 此时调用递归继续向下一层搜索# path和result保持不变# 关键点在于更新目标值为target-candidates[i]表示剩余还需要凑的目标值# 本题更关键的更新begin为i# 因为candidates[i]可以被重复选择所以暂时不要跳到下一个i 1self.__DFS(candidates, target - candidates[i], i, path, result)# 当下一层递归返回后说明当前节点下的所有可重复选# 可能情况都已经探索完成# 将path的最后一个元素弹出恢复到添加该元素之前的状态# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()这样修改后__DFS 作为 Solution 类的一个正常方法可以在 combinationSum 方法中正确被调用代码应该能按照预期执行回溯算法来解决组合总和问题。
如果不将 __DFS 方法设置为与 combinationSum 平级即作为 Solution 类的直接方法而是想在 combinationSum 方法内部定义并使用类似功能的内部函数来实现回溯逻辑也是可以的但需要做一些调整主要是利用闭包的特性来实现。以下是一种修改后的示例代码
from typing import Listclass Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:主函数用于调用内部函数实现回溯来解决组合问题并返回最终结果:param candidates: 无重复元素的整数数组从中选取数字组成满足条件target的组合:param target: 目标整数要使得选取的数字组合的加和达到的值:return: 满足条件的所有不同组合的列表每个组合都是一个整数列表# 特解candidates空集if len(candidates) 0:return []# 对候选数组candidates进行预先排序方便后续剪枝操作candidates.sort()# 准备回溯函数的参数path [] # 记录当前正在生成的一种数字组合情况初始是空列表result [] # 存储最终所有满足条件的数字组合初始是空列表# 定义内部函数利用闭包访问外部函数的变量def inner_DFS(begin):nonlocal path, result, candidates, target# 先对path(上次递归得到的一条路)进行拷贝# 避免后续操作中直接修改传入的path对象# 因为python中列表是可变对象传参时可能出现意外修改情况path path.copy()# 设置递归出口当目标值target0# 说明当前path中的数字组合已经满足和为目标值的条件# 找到了一种满足条件的组合if target 0:result.append(path)return# 遍历从begin位置开始的candidates中的元素# 逐个尝试作为组合的一部分for i in range(begin, len(candidates)):# 剪枝如果当前值特别大走到这个值的时候直接超过了target# 即target - candidates[i] 0# 此路不通returnif target - candidates[i] 0:return# 否则将当前数值candidates[i]添加到path记录正在尝试的组合情况path.append(candidates[i])# 添加后相当于走到了下一个岔路口# 此时调用内部函数自身进行递归继续向下一层搜索# 注意这里调用的是内部函数inner_DFS不是之前的平级方法__DFSinner_DFS(i)# 当下一层递归返回后说明当前节点下的所有可重复选# 可能情况都已经探索完成# 将path的最后一个元素弹出恢复到添加该元素之前的状态# 以便尝试下一个数字作为组合的一部分# 继续生成其他可能的满足条件的数字组合path.pop()# 调用内部函数开始回溯过程初始begin为0inner_DFS(0)return result
——————————————————————————
超时在上述代码中
我们在 combinationSum 方法内部定义了一个名为 inner_DFS 的内部函数它通过 nonlocal 关键字声明了对外部函数combinationSum中的一些变量path、result、candidates、target的引用这样就可以在内部函数中访问和修改这些外部变量实现类似之前 __DFS 方法的功能。在 combinationSum 方法中通过调用 inner_DFS(0) 来启动回溯过程就像之前调用 __DFS 方法一样。
这种方式利用了闭包的特性使得在方法内部定义的函数也能够访问和操作外部函数的相关变量从而实现回溯算法来解决组合总和问题但整体代码结构相对来说可能没有将 __DFS 作为平级方法那么清晰直观所以在实际应用中更常见的还是将相关的辅助方法定义为类的直接方法平级以便于代码的理解和维护。
