题解 | #没有重复项数字的全排列#

1、解题思路总结：

1）其实这个题最难的是在头脑里面有这个一个大概思路，就是这个递归是怎么走的！

其实，就像上面我写的红色的文字，就是具体走的步骤：1-->16，是一个深度递归的过程，从上到下，从左到右。

2）i=1， 没有显示，其实是有的，只是交互的是自己！

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        Arrays.sort(num);
        int size = num.length;
        for(int n : num) {
            output.add(n);
        }
        backtrack(size, output, res, 0);
        return res;
    }

    public void backtrack(int size, List<Integer> output,ArrayList<ArrayList<Integer>> res , int first) {
        if(first == size) {
            res.add(new ArrayList<Integer>(output));
            return;
        }
        for(int i=first; i<size; i++) {
            Collections.swap(output, first, i);
            backtrack(size, output, res, first+1);
            Collections.swap(output, first, i); //这里前后没有区别！
        }
    }

}