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

import java.util.*;


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

    }
    public void backTrack(int[] num,LinkedList<Integer> list,boolean[] used){
        //递归结束的条件
        if(list.size()==num.length){
            res.add(new ArrayList<>(list));
        }
        //函数逻辑
        //没有出现过的数字，加入数组，之前我们用的list.contains,但是现在有重复元素了，所有不能用了，我们现在用used[i]这个标识，为true表示加过了，跳过i
        for(int i=0;i<num.length;i++){
            if(used[i]){
                continue;
            }
            //当前的值和上一个添加的值相等
            if(i>0&&num[i]==num[i-1]&&used[i-1]){
                continue;
            }
            list.add(num[i]);
            //添加完了 将该数字的标识改成用过了
            used[i]=true;
            backTrack(num,list,used);
            //回溯
            list.removeLast();
            //下一分支
             used[i]=false;
        }
    }

}