回溯

回溯

🟧概述

🔻含义： 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 回溯 返回，尝试别的路径

🔻试用场景： 排列组合、优化穷举等

🔻时间复杂度： 具体问题具体分析

🔻空间复杂度： 递归枚举需要用到栈

🔻注意事项：

🔸单个path回溯完毕后要删除上一次回溯的节点:path.remove(path.size()-1);

🔸结果集收集的条件:if(终止条件) res.add(new ArrayList(path));

🔸去重的条件:if(去重条件) continue;

🔸每个组合中的值用是否能重复使用 -> 下一次回溯的起点idx

🔸去重的条件和方式

🔸每个组合中的值用是否能重复使用：不能重复用:handle(s,i+1);能重复:handle(s,i);

🔸解集不能包含重复的组合：Arrays.sort(nums);➕if(i>idx&&nums[i]==nums[i-1]&&!vis[i-1]||vis[i])continue;

🔸下一次回溯的起点idx：一般是和题目和能否重复使用相关 不能重复用:handle(s,i+1);能重复:handle(s,i);

🟧模板

📌通用模板

class Solution {

    List<List<Integer>> res =new ArrayList();
    List<Integer> path = new ArrayList();
    int[]/Set/Map visted;//去重变量

    public List<List<Integer>> Question(int[]nums) {
        backTrace(nums);
        return res;
    }

    void backTrace(int[]nums,int idx){

        if(终止条件) res.add(new ArrayList(path));
        if(去重条件) continue;

        for(int i=idx;i<nums.length;++i){
            path.add(nums[i]);
            handle(nums,i);
            path.remove(path.size()-1);
        }

    }
}

🟧总结

🔻思考1:为什么使用回溯?

🔸回溯中采用剪枝的方式去优化暴力枚举降低时间复杂度

🔻思考2:本质?

🔸采用剪枝和其他去重变量做选择式枚举

🔸基于深度优先搜索和约束函数的问题求解方法

🔻思考3:实际应用?

🔸排列组合问题

🔻思考4:限制条件?

🔸剪枝方案和题目的数量大小决定复杂度

🔻思考5:对比穷举法?

🔸回溯法与穷举法有某些联系，它们都是基于试探的。

🔸穷举法:要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。

🔸回溯法:一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。