回溯算法 , 就是 穷举
解决一个回溯问题,实际上就是一个决策树的遍历过程.
路径: 也就是已经做出的选择
选择列表: 也就是你当前可以做的选择
结束条件: 也就是到达决策树底层,无法再做选择的条件.
回溯算法的一个特点: 它不像动态规划存在重叠子问题可以优化,回溯算法就是纯暴力穷举,复杂度一般都很高,不可能低于0(n!),因为穷举整颗决策树是无法避免的.
python代码:
from rich.console import Console
from rich import print
console = Console()
res = []
def permute( nums):
tarck = []
backtrack(nums,tarck)
return res
def backtrack(nums,track):
if (len(track) == len(nums) ):
res.append(track.copy())
console.log( 'nums长度和track长度一致' , style="bold red underline")
print('当前res是: '+ str(res))
return res
for i in nums:
if i in track:
continue
track.append(i)
backtrack(nums,track)
track.pop()
res = permute([1,2,3])
console.log( res , style="bold green ")
# 输出结果: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
dart代码:
List> res = [];
List> permute(List nums){
List track = [] ;
backtrack(nums, track);
return res;
}
void backtrack(List nums, List track){
if (nums.length == track.length){
res.add(track.sublist(0));
print("当前res是: "+res.toString());
return ;
}
for(int i=0;i
if (track.contains(nums[i])){
continue;
}
track.add(nums[i]);
backtrack(nums, track);
track.removeLast();
}
}
void main() {
var xx = permute([1,2,3]);
print(xx);
}
Flutter 写的app, 需要源码可以私信~~
如果觉得《python 动态规划 回溯_回溯算法 - 全排列算法实现(pythondart)》对你有帮助，请点赞、收藏，并留下你的观点哦！
