穷举深搜暴搜回溯剪枝(1)

一)全排列:

46. 全排列 - 力扣（LeetCode）

1)先画出决策树:

越详细越好，就是我们在进行暴力枚举这道题的过程中，如何不重不漏地将所有的情况全部枚举到，把这个思想历程给画下来，就可以了，把每一步的决策树画出来

2)设计代码:

2.1)设计全局变量:就需要看一下这个递归过程中要记录一些什么东西

a)使用一个二维数组在这个题就是保存我们最终的返回值

b)使用一个一维数组int[] path来保存此时路径上的所有的选择，path的作用就是当我在对这棵树做深度优先遍历的时候，记录一下此时路径上的所有选择，遍历到到叶子节点的时候就可以将这个path加入到二维数组中(path.length==nums.length)，

但是向上回溯的时候还需要恢复现场的，就拿最上面的那一个图来说，当我遍历到最下面的123的时候，需要将123这个数存放到二维数组里面，但是向上归上一层的过程中，要把3去掉，再次向上一层归的时候，要把2干掉；

c)此时再来想一下剪枝操作该如何来进行实现呢，此时就需要一个布尔数组，这个布尔数组就是用来帮助我们进行记录这个数是否已经在这个路径中使用过了，布尔数组里面记录下标，判断一下当前这个下标所对应的数是否已经在当前被使用过了

d)所以当我们选择2的时候，我们就应该将布尔类型的1设置成true，意思就是1位置的这个2已经被我使用过了，然后再去遍历当前数组

for(int i=1;i<=3;i++) if(bol[i]==true) path.add(array[i])

2.2)设计dfs函数:仅仅只需要关心某一个节点在干啥即可

就是将整个数组所有的数给枚举一遍如果这个数没有用到过的话，就把这个数放到path后面

2.3)细节问题:

a)回溯:回溯在进行向上归的时候，要把最后一个数给干掉

b)剪枝:向上回溯到上一层的过程中，要把这个数在check数组中重新标记成false

c)递归出口:当我们遇到叶子节点的时候，直接添加结果

写这个递归时候的一个小技巧:在我们进行编写回溯代码的时候，只需要关心每一层在做什么事情即可，只需要写出每一层中相同的函数逻辑即可
class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] bool;
    public List<List<Integer>> permute(int[] nums) {
       ret=new ArrayList<>();
       path=new ArrayList<>();
       bool=new boolean[nums.length];
       dfs(nums);
       return ret;
    }
    public void dfs(int[] nums){
        //在我们的递归函数里面,我们只需要关心每一层在做什么事情就可以了
        if(path.size()==nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
      for(int i=0;i<nums.length;i++){
          if(bool[i]==false){
              path.add(nums[i]);
        bool[i]=true;
        dfs(nums);
        //回溯-->恢复现场
        bool[i]=false;
        path.remove(path.size()-1);
        }
      }
 }
}

二)子集:

78. 子集 - 力扣（LeetCode）

一)解法一:

1)画出决策树:针对于当前元素是否进行选择画出决策树

1)全局变量的设计:

1)使用一个二维数组来保存我们最终计算出来的结果，里面的值保存的就是最终所有的路径

2)使用一个一维数组来保存每一个路径上面的所有字符串

2)dfs的设计:

2.1)我们每一层所做的事情就是不仅要进行传递nums，当进行考虑到每一个值的时候，都需要进行判断当前这个值是选择还是不选择，还需要知道当前我们遍历到了哪一个位置，传递的是这个数对应的下标，只需要考虑这个数选择还是不进行选择

2.2)如果选择了，那么就见这个数添加到path中

path.add(nums[i])

dfs(path，i+1)

如果不选，path终究不会添加任何数字，dfs(path，i+1)

3)细节问题

a)剪枝:

b)回溯:当进行回溯的时候，一定要记得恢复现场path.remove(nums[i])

c)递归出口:仅仅需要考虑到叶子节点的时候，就可以向上返回了当i等于nums.size()的时候

递归的出口也就是说什么时候收集结果
class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> subsets(int[] nums) {
        path=new ArrayList<>();
        ret=new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int i){
        if(i==nums.length){
            ret.add(new ArrayList<>(path));
            return;
        } 
        //选
        path.add(nums[i]);
        dfs(nums,i+1);
        path.remove(path.size()-1);
        //不选,不选的话当前没有path路径中没有加这个数,所以也不需要恢复现场了
        dfs(nums,i+1);
    }
}
二)解法2:

1)画决策树:针对于自己中含有0个元素，1个元素，2个元素来画出决策树，根据元素个数来进行设计决策树，当进行决策的时候只是考虑这个数后面的这个数

在上面的这个决策树中决策树中每一个结点的值都是我们想要的结果

2)设计代码:

a)全局变量:仍然搞一个二维数组来返回最终的结果，使用一维数组来存放最终的结果

b)dfs:找一找每一个节点都在做什么事情，都是从当前这个位置开始向后找到元素进行拼接只是把后面的数添加到path中

dfs(nums，pos):代表着你接下来一层要从哪里开始进行枚举

for(int i=pos；i<nums.length；i++)

{

path.add(nums[i])；

dfs(nums，i+1)；

//返回现场

path.remove(path.size()-1)；

}

c)细节问题，回溯剪枝递归出口:

回溯:进入到函数体的时候，都需要添加结果
class Solution {
    List<Integer> path;
    List<List<Integer>> ret;
    public List<List<Integer>> subsets(int[] nums) {
        this.path=new ArrayList<>();
        this.ret=new ArrayList<>();
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int index){
        ret.add(new ArrayList<>(path));
//在这里面我们只是进行考虑决策树上面的每一个节点都在干什么事情,index表示当前要传入元素的下一个位置
        for(int i=index;i<nums.length;i++){//i代表的是元素的下标
             path.add(nums[i]);
             dfs(nums,i+1);
             path.remove(path.size()-1);
        }
    }
}

三)找出所有自己的异或总和在求和

1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）

1)画出决策树:

2)设计代码:

a)全局变量

1)使用sum来保存程序最终返回的结果，每一次递归进入到一个函数的时候，就把里面的异或和给加上

2)path当前数的异或结果

b)dfs

参数就是从哪一个位置开始进行枚举，还有数组的引用

c)回溯剪枝递归出口

1)回溯就是假设当我在第二层计算完这个1和2异或的结果之后或者在第三层将结果计算完成之后要向上返回，此时可以使用异或方法中的消消乐规则来进行计算，两个相同的数字进行异或之后这两个数就进行相互抵消了

2)假设我在第二层存放的就是1和2异或的结果，当向上返回到第一层的时候，恢复现场的时候只需要将这个2异或就可以退回到上一层了

3)递归出口就是每一次进入到这个函数的时候都需要+=path
class Solution {
    List<Integer> path;
    int sum=0;
    public int subsetXORSum(int[] nums) {
        path=new ArrayList<>();
        dfs(nums,0);
        return sum;
    }
    public void dfs(int[] nums,int index){
        if(index==nums.length){
            int result=0;
            for(int i=0;i<path.size();i++){
                result=result^path.get(i);
            }
            sum+=result;
            return;
        }
    path.add(nums[index]);
    dfs(nums,index+1);
    path.remove(path.size()-1);
    dfs(nums,index+1);
    }
}

四)K个一组反转链表

25. K 个一组翻转链表 - 力扣（LeetCode）

算法视频讲解:BM3 链表中的节点每k个一组翻转_哔哩哔哩_bilibili

算法原理:

重复子问题:K个一组反转链表

每k个一组进行反转链表

递归写法:

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
//1.采用递归的方式来进行解决,返回值是链表的头节点
    ListNode prev=null;
    ListNode current=head;
    ListNode tail=head;
//2.先进行找到递归的出口,既然是k各一组反转链表,那么链表至少要满足k个,tail指针是最终指向下一组反转链表的头结点,最终可以使他作为反转链表的终止条件
    for(int i=0;i<k;i++){
        if(tail==null) return head;
        tail=tail.next;
    }
//3.根据重复子问题的思路来编写递归的代码,其实就是反转链表的逻辑
    while(current!=tail){
        ListNode CurNext=current.next;
        current.next=prev;
        prev=current;
        current=CurNext;
    }
//反转链表完成之后最终current指向下一组k个反转链表的终止节点,prev指向此次反转链表的最后一个节点
//4.进行递归操作,进行下一组反转链表的操作,返回的是下一组反转链表的头结点
head.next=reverseKGroup(tail,k);
  return prev;
    }
}

五)全排列(2)

47. 全排列 II - 力扣（LeetCode）

我们此时就拿1 1 1 2来进行举例:

1)画出决策树:决策树画得越详细越好，根据每一个位置选择哪些数来完成问题

1.1)首先画出决策树的时候首先选取第一个数放在第一个位置上，第一个位置有四个数可以进行选择，首先在这个第一个数字选择过程中过程中就涉及到了剪枝操作:我们的第一个位置可以选择第一个1，第二个1，第三个1，第四个2，此时我们只是可以保留第一个位置填写第1个1和第四个2，首先在第一个位置是不能选择出重复的数的，因为这会导致后面的选法全部都是一样的，所以总结同一个节点的所有分支中，相同的节点只能选择1次；

比如说我们选择第一个1，那么后面的数就可以从1 1 2里面随便挑，如果选择第二个1后面只能在1 1 2中选，势必会出现重复元素，所以我们只需要保留第一个1，剩余的两个1在第一层全部剪掉，同一个节点的所有分支中，相同的元素只能选择1次

1.2)同一个数只能能够使用一次，可以使用check布尔数组来进行解决，当我们曾经使用过第一个1的时候，就把这个第一个1标记成一个true，接下来在下一层进行再从数组的第一个位置开始进行枚举的时候就看一下，如果这里面是true，说明这个第一个1已经被使用过了，那么就直接将这个支剪掉

2)实现剪枝:

1)只关心不合法的分支:什么时候不执行这个递归，就是当执行这个递归的时候再来判断一下这个值是否合法不合法就直接continue即可

a)当check[i]==true的时候，说明当前位置的元素已经被使用过了，所以这个位置的值已经不能使用了

b)如果nums[i]==nums[i-1]当前元素和前面的元素相同，这时候就不会再i位置的元素的了，用了，所以一定要将数组元素，这样才可以把相同的元素放在一堆；

也就是说nums[i]==nums[i-1]并且check[i-1]==false才可以认为这是相同的元素

c)如果nums[i]==nums[i-1]并且check[i-1]==true其实是属于不同的数的，这个nums[i-1]其实已经在上一层被使用过了

d)nums[i]==nums[i-1]&&check[i-1]==false&&i!=0(防止数组越界)(如果i==0，那么当前这个元素一定是可以进行使用的)，说明出现了相同的元素，只是保留一个即可，但是为了让相同的元素挨在一起

所以说当我们的程序出现上述两种情况中的一种的时候，直接让我们的程序continue不执行当前的dfs操作

2)只关心合法的分支:什么时候进入到这个递归

a)当前这个元素没有被使用过

b)当前这个数和前面的这个数不一样的时候，这个数肯定是可以进行选择的

c)还有就是说我这个数虽然可以和前面的数一样，但是我前面的这个数已经被使用过了，那么当前的数也是可以使用的

check[i]=false(当前分支没有被使用过)||(i==0||nums[i]!=nums[i-1]||check[i-1]==true)
class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] bool;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret=new ArrayList<>();
        path=new ArrayList<>();
        bool=new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,0);
        return ret;
    }
    public void dfs(int[] nums,int pos){
        if(pos==nums.length){
            ret.add(new ArrayList<>(path));
            return;
        } 
        for(int i=0;i<nums.length;i++){
    if(bool[i]==false&&(i==0||nums[i]!=nums[i-1]||bool[i-1]!=false))
    {
        bool[i]=true;
        path.add(nums[i]);
        dfs(nums,pos+1);
        bool[i]=false;
        path.remove(path.size()-1);
    }
        }
    }
}