引言

最近很长时间没有刷题，忘了很多，正好遇到一道老朋友 数组全排列；
恰好用到了回溯，今天回顾一下；

算法题分析

题46

本题 引自：leetcode 46

分析

首先，每个数可以用填空来考虑

讲到了树，可以说一下递归和回溯

回溯就是树的递归；
我们在调用的过程中，先填数，如果达到返回条件，选择其它没有选择的数字

算法R

    @Test
    public void permute() {
        int[] nums = {1,2,3};
        //实现全排列
        int len = nums.length;
        int depth = 0;
        boolean[] isUsed = new boolean[len];
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        DFS(depth, isUsed, result, path, len, nums);
        System.out.println(result);
    }
    //判断下 Deque ArrayDeque  ArrayList三者区别: 这里使用双端队列Deque是为了实现removeLast方法
    //Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。
    private void DFS(int depth, boolean[] isUsed, List<List<Integer>> result, Deque<Integer> path, int len, int[] nums) {
        if(depth==len){
            result.add(new ArrayList<>(path)); //为什么需要clone，引用类型， 本身就是指向地址的，需要new一个新空间
            return;
        }

        for (int i = 0; i < len; i++) {
            if(isUsed[i])continue;
            path.add(nums[i]);
            isUsed[i]=true;
            DFS(depth+1, isUsed, result, path, len, nums);//这里的 depth++和++depth，还有depth+1 下面给了例子
            path.removeLast();
            isUsed[i]=false;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    @Test
    public void ss(){
        int a = 0,b = 0,c = 0,d = 0,e = 0;
        pop(a++, b--,++c, --d, e+1);

    }

    private void pop(int i, int i1, int i2, int i3, int i4) {
        System.out.println("pop" + i ); //  
        System.out.println("pop" + i1 ); //a++和b--都是直接调用a，再做操作
        System.out.println("pop" + i2 );
        System.out.println("pop" + i3 );//++a和--b都是做操作，调用a，但是，对于递归，不要这样做，因为返回时会覆盖，这个打个断点，我不是很确定，后面debug，此处留坑
        System.out.println("pop" + i4 );
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14