深度对比深度优先----全排列例子

数据结构与算法

1.使用ArrayList保存item

 public static void dfs(int[] nums, int[] book, int step, ArrayList<Integer> item) {
        if (step == nums.length) {
            System.out.println(Arrays.toString(item.toArray()));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (book[i] == 0) {
                item.add(nums[i]);
                book[i] = 1;
                dfs(nums, book, step + 1, item);
                book[i] = 0;
//                item.remove(item.size() - 1);
            }
        }
    }

输出是：

[1, 2, 3, 4]
[1, 2, 3, 4, 4, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3, 3, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3, 3, 2, 2, 1, 3]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3, 3, 2, 2, 1, 3, 3, 1]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3, 3, 2, 2, 1, 3, 3, 1, 3, 1, 2]
[1, 2, 3, 4, 4, 3, 3, 2, 4, 4, 2, 4, 2, 3, 3, 2, 2, 1, 3, 4, 4, 3, 3, 1, 4, 4, 1, 4, 1, 3, 3, 1, 3, 1, 2, 4, 4, 2, 2, 1, 4, 4, 1, 4, 1, 2, 2, 1, 4, 1, 2, 3, 3, 2, 2, 1, 3, 3, 1, 3, 1, 2, 2, 1]

因为ArrayList对象一直是持有引用，要是不remove掉里面的数据相当于是内存泄漏了

2.数组存放数据

    public static void dfs1(int[] nums, int[] book, int step, int[] result) {
        if (step == nums.length) {
            System.out.println(Arrays.toString(result));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (book[i] == 0) {
                result[step] = nums[i];
                book[i] = 1;
                dfs1(nums, book, step + 1, result);
                book[i] = 0;
//                result[step]=0;
            }
        }
    }

注释与不注释掉那一句都是无所谓的。

step只是起以一个记步的作用