17_回溯算法（Back_Traceing）

简单描述

回溯算法是在遍历树枝，DFS是在遍历节点；

优势

代码易于理解

劣势

不想动动态规划存在重叠的子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般比较高

伪代码

result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择：将该选择从选择列表中移除，路径add选择
backtrack(路径, 选择列表)
撤销选择：路径remove选择，将该选择加入选择列表

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

写backtrack函数时，需要维护走过的“路径”和当前可以做的“选择列表”，当触发“结束条件”时，将“路径”记入结果集。

使用场景

• 有重叠子问题的用动态规划，没有动态子问题的可以用回溯算法

例子-全排列问题

/**
* 全排列问题
* 时间复杂度：O(n!)
* 空间复杂度：O(n)
*
* @param nums
* @return
*/
public List<List<Integer>> permute(int[] nums) {
// 初始化一个结果集
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
// 如果数组为空，直接返回结果集
if (nums.length == 0) {
return res;
}
// 调用递归函数，传入结果集，数组，空的路径
backtrace(nums, res, path);
return res;
}
// 递归函数
private void backtrace(int[] nums, List<List<Integer>> res, LinkedList<Integer> path) {
// 如果路径长度等于数组长度，说明已经遍历完了
if (path.size() == nums.length) {
// 把路径加入结果集
res.add(new ArrayList<>(path));
return;
}
// 遍历数组
for (int i = 0; i < nums.length; i++) {
// 如果路径中已经包含当前元素，跳过
if (path.contains(nums[i])) {
continue;
}
// 把当前元素加入路径
path.add(nums[i]);
// 递归调用
backtrace(nums, res, path);
// 回溯，把当前元素从路径中移除
path.removeLast();
}
}

最后

以上就是紧张奇迹为你收集整理的算法类型描述以及举例17_回溯算法（Back_Traceing）17_回溯算法（Back_Traceing）的全部内容，希望文章能够帮你解决算法类型描述以及举例17_回溯算法（Back_Traceing）17_回溯算法（Back_Traceing）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。