递归、搜索与回溯算法——穷举vs暴搜vs深搜

此篇文章与大家分享递归、搜索与回溯算法关于穷举vs暴搜vs深搜的专题
如果有不足的或者错误的请您指出!

1.全排列

题目:全排列

1.1解析

假设nums = [1,2,3]
对于这种列举的题,我们的第一步通常是画决策树

如图所示,我们按照要求将决策树显示画出来后,可以发现,实际上就是我们前面讲过的二叉树的遍历
只不过之前的题目已经帮我们把树给画好了,但是这类题目需要我们自己画
按照图,我们发现,实际上对于每一个节点,我们做的事情都是一样的,都是针对三种情况进行讨论,那么我们就可以使用递归来做
此时有几个主要的细节问题
(1)剪枝:如图所示,我们有一些枝干是不用去递归的(图中的红叉叉),就是我们已经讨论过的数字就不能再次讨论的.
我们可以创建一个布尔类型数组,长度与nums数组一样,用于表示当前下标在nums中的值是否已经讨论过
(2)记录:我们用path来记录遍历每一条枝干的节点的值,当path里面值的长度 = nums数组的长度是,我们就将path插入到返回列表中
(3)回溯:我们在递归完某个枝干后,需要将path还原成原来的样子

1.2题解

class Solution {
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];
        dfs(nums);
        return ret;
    }
    private void dfs(int[] nums) {
        if(path.size() == nums.length) {
            ret.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(check[i] == false) {
                path.add(nums[i]);
                check[i] = true;
                dfs(nums);

                //回溯
                check[i] = false;
                path.remove(path.size()-1);
            }
        }
    }
}

2.子集

题目:子集

2.1解析

2.1.1解法1

假设数组nums = [1,2,3]
我们直接画决策树

此时我们可以发现,决策树的叶子节点就是我们想要的结果,此时叶子节点也就是递归的出口
而每一个节点做的事情都是一样的,就是选与不选进行分枝
但是此处我们的递归函数还要传一个参数,就是告诉下一次递归选的数是哪个

2.1.2解法1代码

class Solution {
    private List<List<Integer>> ret = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return ret;
    }
    private void dfs(int[] nums,int pos) {
        if(pos == nums.length){
            ret.add(new ArrayList(path));
            return;
        }
        path.add(nums[pos]);
        dfs(nums,pos+1);
        path.remove(path.size()-1);
        dfs(nums,pos+1);
    }
}

2.1.3解法2

如图所示的决策图,我们可以以path中元素的个数为标准进行递归,每次递归都从当前传进去的pos开始添加元素,就能保证不重复
此时我们会发现,每一个节点都是我们要的结果,这种解法相对于解法1来说"剪枝"了很多情况

2.1.4解法2代码

class Solution {
    private List<List<Integer>> ret = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return ret;
    }
    private void dfs(int[] nums,int pos) {
        ret.add(new ArrayList<>(path));
        for(int i = pos; i < nums.length; i++){
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}