回溯算法几个经典例子,回溯算法 java
1.回溯算法框架例程回溯可以理解为暴力递归剪枝。解决一个回溯问题，其实就是一个决策树的遍历过程，需要大致分为以下三步。
路径：所做选择的列表：即当前选择的结束条件：即到达决策树的底部，不能再做选择。result=[]def回溯：如果满足结束条件：result.add (path)返回选择列表中的选择：进行选择回溯(path，selection list)并取消选择。2.完成排列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
num中的所有整数都互不相同。
解决方案：
类别解决方案：
def permute(self，nums:List[int])-List[List[int]]:
res=[]
track=[]
self.backtrack(res，track，nums)
返回资源
定义回溯(自身、res、track、nums):
#糟糕的情况
如果len(track)==len(nums):
res.append(轨道[:])
返回
对于范围内的I(0，len(nums)):
如果nums[i]在轨道上：
继续
track.append(nums[i])
self.backtrack(res，track，nums)
Track.pop() #撤销条件
3.子集
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中的所有元素互不相同。
解决方案：
类别解决方案：
def子集(self，nums:List[int])-List[List[int]]:
res=[]
track=[]
self.backtrack(res，nums，track，0)
返回资源
定义回溯(自身、res、nums、跟踪、开始):
开始：控制分支的增长以避免重复子集。
Track:记录从根节点到每个节点的路径值。
[]也是它的一个子集。
res.append(轨道[:])
#基础案例
if start==len(nums):
返回
对于范围内的I(start，len(nums)):
track.append(nums[i])
self.backtrack(res，nums，track，i 1)
track.pop()
4.括号生成
22.括号生成
数字n代表生成的括号的对数。请设计一个能生成所有可能有效的括号组合的函数。
示例1:
输入：n=3
Output: [((())， (() ())， (()) ()，()()]
示例2:
输入：n=1
输出：[()]
1=n=8
解决方案：
类别解决方案：
def generate parathesis(self，n: int) - List[str]:
结果=[]
self.backtracking(n，result，0，0，)
回送结果
定义回溯(self，n，result，left，right，s):
#如果右括号的数量大于左括号的数量，则不符合有效的括号组合。
如果右向左：
返回
如果左==n且右==n:
结果.追加
返回
#以左括号开始。
如果向左n:
self.backtracking(n，result，left 1，right，s ()
#右括号比左括号小，加右括号。
如果右向左：
self.backtracking(n，result，left，right 1，s ))
转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。