回溯法总结

约定不等于承诺〃 2024-04-03 09:50 59阅读 0赞

回溯法分为组合,子集,排列等问题,下面分别就这几个问题进行总结.

1.总体架构

总体来说,回溯法像是在遍历一棵树,而这棵树的深度,由回溯的终止条件以及for循环内部的变量控制组成

LinkedList<Integer> temp = new LinkedList<>();//暂存数据的链表
    List<List<Integer>> re = new ArrayList<>();//待返回的结果集
    
    public void backtracing(int[] nums, int startIndex, int[] used){
        //三个参数分别表示 nums待遍历的数组,通常是题目中给出的数组
        //startIndex遍历的开始位置,并不一定是必须的,取决于题目类型(如果是一个数组的组合问题则一般需 
        //要)
        //used 则用于父子结点间去重,在同父亲结点间的去重则在本函数内部定义一个hashMap或者used数组
        if(){
        //此处填写的是满足遍历结束的条件,通常为temp数组(或者linkedList)的长度满足给定的条件
        //将满足条件的temp加入到re中
        re.add(new ArrayList(temp));
        //在添加结束后是否是使用return则需要根据题目的条件判断:
        //如果是全排列,组合问题这种,也就是说都已经遍历到这个树的叶子结点的这种问题,应当采用return
        //而若是子序列问题,比如寻找递增子序列(力扣491),整棵树还需要继续向下进行遍历,则不需要return
        }     
        
        //当然如果我们为了达到在同父结点的层内去重的目的,要在此处建立一个HashMap,或者used数组,
        //不过需要注意的是,如果再这里建立的uesed数组,他的意义和传参进来的used数组并不一样,传参进来的 
        //used数组是用来标识数组中的下标,也就是说,数组中的数字按顺序来看是否被使用,而此处则是标记同        
        样的 
        //数字是否被使用.所以used的数组的范围应该是nums数组中数字的范围,而不是nums数组的长度,传参进 
        //来的used的范围是nums数组长度(目的是为了一对一表示数组中的元素)此处的给出示例:力扣46题,以及 
        //自己写的力扣47题的used数组,(自己写的放在了力扣刷题专栏中)
        HashMAP<Integer,Integer> map = new HashMap<>();//本层去重(如果需要)
        //这里需要判断map中的key和value的相对关系了
        if(map.getOrDefault(nums[i],0) >= 1){
            //这里满足当前条件则说明在本层,这个数字已经出现过一次了
            continue;//如果满足条件的话,且需要去重
        }
        for(int i = ?; i < nums.length; i++){
            //在此处,i的起始值是一个问号,需要根据是否使用startIndex来进行修改,如果使用startIndex
            //那么i的值为startIdex,否则为0
            //对于是否使用startIndex给出示例: 对于[1,2,3]这个数组来说,如果求的是子序列问题,或者组合 
            //问题,也就是说只能出现[1,2],[1,3]这种按照原始的相对顺序出现,则需要startIndex,若求的是 
            //排列问题,也就是说要求[3,2,1]这种情况出现,则不能使用startIndex,因为要是使用了,则 3 对 
            //应着最后的位置,没办法再向前遍历到1,2的位置
            
            if(添加一些判断条件,比如要求递增序列){
                
            }
            temp.add(nums[i]);
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
            //!!!!!!
            //注意这个map不回溯!因为层间去重,回溯就没意义了!!!!!!!!!
            used[i] = 1 ;//将数组的当前位置记为使用过的形式,这种遍历方式是会让子元素不再使用
                         //解决的问题主要是当出现重复的数字的时候,不超过重复次数的使用重复数字
            backtracing(nums, i + 1, used);//注意此处若采用了startIndex则向下一层应该是i+1,而不 
                                           //是startIndex+1
            temp.remove(temp.size() - 1);//撤销修改
            used[i] = 0;
        }
    
    
    }

2.组合

[力扣][Link 1]

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母

class Solution {
    
        List<String> re = new ArrayList<>();
        public List<String> letterCombinations(String digits) {
            if (digits == null || digits.length() == 0) {
                return re;
            }
            //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
            String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            //迭代处理
            backTracking(digits, numString, 0);
            return re;
        }
    
        StringBuilder t = new StringBuilder();
        public void backTracking(String digits, String[]numString, int cur){
            if(cur == digits.length()){
                re.add(t.toString());
                return;
            }
            String str = numString[digits.charAt(cur) - '0'];
            for(int i = 0; i < str.length(); i++){
                t.append(str.charAt(i));
                backTracking(digits,numString,cur+1);
                t.deleteCharAt(t.length()-1);
            }
        }
    
    }

3.子序列问题

此处的子序列问题使用了层间去重的操作

层间去重使用了两个版本的方法,分别为HashMap以及used数组,注意此处的used数组和**排列问题**的used数组**并不一样**,无论从意义和大小来说.

[491. 递增子序列][491.]

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

输入：nums = [4,6,7,7]
    输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

class Solution {
        LinkedList<Integer> li = new LinkedList<>();
        List<List<Integer>> re = new ArrayList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {
            get(nums, 0);
            return re;
        }
        public void get(int[] nums, int startIndex){
            if(li.size() >= 2){
                re.add(new ArrayList(li));
                // return;
            }
            HashMap<Integer, Integer> map = new HashMap<>();
    
            for(int i = startIndex; i < nums.length; i++){
                if (li.size() > 0 && nums[i] < li.getLast()){
                    continue;
                }    
                if (map.getOrDefault(nums[i], 0) >= 1){
                    continue;//说明使用过了
                }
    
                li.add(nums[i]);
                map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
                get(nums, i + 1);
                li.remove(li.size() - 1);
        }
        }
    }

class Solution {
        private List<Integer> path = new ArrayList<>();
        private List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> findSubsequences(int[] nums) {
            backtracking(nums,0);
            return res;
        }
    
        private void backtracking (int[] nums, int start) {
            if (path.size() > 1) {
                res.add(new ArrayList<>(path));
            }
    
            int[] used = new int[201];
            for (int i = start; i < nums.length; i++) {
                if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
                        (used[nums[i] + 100] == 1)) continue;
                used[nums[i] + 100] = 1;
                path.add(nums[i]);
                backtracking(nums, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

4.排列问题

[47. 全排列 II][47. _ II]

给定一个可包含重复数字的序列 `nums` ，***按任意顺序*** 返回所有不重复的全排列。

输入：nums = [1,1,2]
    输出：
    [[1,1,2],
     [1,2,1],
     [2,1,1]]

输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

自己写的代码段如下

class Solution {
        LinkedList<Integer> temp = new LinkedList<>();
        List<List<Integer>> re = new ArrayList<>();
        public List<List<Integer>> permuteUnique(int[] nums) {
            int[] used = new int[nums.length];
            get(nums, used);
            return re;
        }
    
        public void get(int[] nums, int[] used){
            if(temp.size() == nums.length){
                re.add(new ArrayList(temp));
                return;
            }
    
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i < nums.length; i++){
                //优先判断是否是使用过的数字used数组(因为如果先判断了是否是层间去重,可能直接就跳过了)
                //如果使用过则continue而不是return,因为continue就直接跳过向下一层的循环了
                if(used[i] == 1 || map.getOrDefault(nums[i],0) >= 1){//层间重复的数字,跳过
                    continue;
                }
                used[i] = 1;
                temp.add(nums[i]);
                map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
                get(nums,used);
                used[i] = 0;//回溯
                temp.remove(temp.size() - 1);
                // map不回溯
            }
        }
    
    }

解释:hashMap负责层间去重,used负责重复元素的使用次数不超过重复次数~

以1 1 3为例子画图说明

![d1faa858370e447bbbf9a41c3f8c6ae8.png][]

5.回溯代码是否设置返回值的问题:

如果是要寻找出全部的路径则不用添加返回值,但是要是只需要找到一条路径,就应当设置返回值.类比树的返回值设置.

> 1.如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回
> 
> 2.如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
> 
> 3.如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

带返回值的回溯法举例如下:

[332. 重新安排行程][332.]

题目描述:

![9a78ff9133534f1d8ce93f9591ad0ee3.png][]

对应的代码如下:

class Solution {
        private LinkedList<String> re ;//在回溯过程中如果符合要求就直接返回
        private LinkedList<String> path = new LinkedList<>();
        public List<String> findItinerary(List<List<String>> tickets) {
            //按照第二个元素的升序排列
            Collections.sort(tickets, (a,b)->(a.get(1).compareTo(b.get(1))));
            path.add("JFK");
            boolean[] used = new boolean[tickets.size()];
            backtracing((ArrayList)tickets, path, used);
            return re;
        }
    
        public boolean backtracing(ArrayList<List<String>> tickets, LinkedList path, boolean[] used){
            if(path.size() == tickets.size() + 1){
                re = new LinkedList(path);
                return true;
            }
    
            for(int i = 0 ; i < tickets.size(); i++){
                if(!used[i] && tickets.get(i).get(0).equals(path.getLast())){
                    path.add(tickets.get(i).get(1));//没被使用过
                    used[i] = true;
    
                    if(backtracing(tickets, path, used)){
                        return true;
                    }
    
                    used[i] = false;
                    path.remove(path.size()-1);
                }
                
            }
            return false;
        }
    }

[Link 1]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
[491.]: https://leetcode.cn/problems/increasing-subsequences/
[47. _ II]: https://leetcode.cn/problems/permutations-ii/
[d1faa858370e447bbbf9a41c3f8c6ae8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3d8566ff088a4ee0b27a36990fc27763.png
[332.]: https://leetcode.cn/problems/reconstruct-itinerary/
[9a78ff9133534f1d8ce93f9591ad0ee3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/5054939d24044cb0b5ca816fb0165779.png