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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[num.length];
        //先排序
        sortIntArray(num);

        // for(int i=0;i<num.length;i++){
        //     System.out.println(num[i]);
        // }
        //开始递归
        sortAllResult(num, used, new ArrayList<>(), result);
        return result;
    }

    public void sortAllResult(int[] num, boolean[] used, ArrayList<Integer> curList,
                              ArrayList<ArrayList<Integer>> result) {
        //将之前已填充的数带过来
        ArrayList<Integer> localList = new ArrayList<>(curList);
        //这一遍添加中，已经加过的数字，记录下来，后面不再以这个数字开头
        ArrayList<Integer> curStartInt = new ArrayList<>();
        if (localList.size() == num.length) {
            //结束递归
            result.add(localList);
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!used[i] && !curStartInt.contains(num[i])) {
                curStartInt.add(num[i]);
                localList.add(num[i]);
                used[i] = true;
                sortAllResult(num, used, localList, result);
                used[i] = false;
                localList.remove(localList.size() - 1);
            }
        }
    }

    public void sortIntArray(int[] num) {
        if (num.length < 1) {
            return;
        }
        for (int j = 0; j < num.length; j++) {
            for (int i = j+1; i < num.length; i++) {
                if (num[i] < num[j]) {
                    int temp = num[j];
                    num[j] = num[i];
                    num[i] = temp;
                }
            }
        }

    }
}