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

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>> ans=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> t=new ArrayList<Integer>();
        int[] v=new int[num.length];
        // for(int i=0;i<v.length;i++){
        //     v[i]=0;
        // }
        Arrays.sort(num); //先排序，保证字典排序
        dfs(ans,t,num,v);
        return ans;
    }
    public void dfs(ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> t,int[]num,int[] v){
        if(t.size()==num.length){
            if(ans.contains(t))return;
            ans.add(new ArrayList<>(t));//易错点：添加t的副本，而不是t的引用
            return;
        }
        for(int i=0;i<num.length;i++){
            if(v[i]==0){
                v[i]=1;
                t.add(num[i]);
                dfs(ans,t,num,v);
                t.remove(t.size()-1); //移除最后一个元素
                v[i]=0;
            }
        }
    }
}