回溯法总结-蒲公英云

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

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.组合

力扣

给定一个仅包含数字 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. 递增子序列

给你一个整数数组 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

给定一个可包含重复数字的序列 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为例子画图说明

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

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

1.如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回

2.如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。

3.如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

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

332. 重新安排行程

题目描述:

对应的代码如下:

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;
    }
}