NC42：有重复项数字的所有排列

拓展：有重复项字符的所有排列
解法1：Boolean+数组记录

import java.lang.*;
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        if(num == null || num.length == 0){
            return rst;
        }
        Arrays.sort(num);
        boolean[] visit = new boolean[num.length];
        ArrayList<Integer> list = new ArrayList<>();
        fun(rst,list,visit,num);
        return rst;
    }

    public void fun(ArrayList<ArrayList<Integer>> rst,ArrayList<Integer> list,boolean[] visit,int[] num){
        if(list.size() == num.length){
            rst.add(new ArrayList<Integer>(list));
        }
        for(int i = 0;i<num.length ;i++){
            if(visit[i] == true || (i!=0&&num[i] == num[i-1] )&&visit[i-1] == false){
                continue;
            }
            visit[i] = true;
            list.add(num[i]);
            fun(rst,list,visit,num);
            list.remove(list.size()-1);
            visit[i] = false;
        }
    }
}

解法2：HashSet+交换

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        if (num == null || num.length < 1) 
            return res;
        Arrays.sort(num);
        process2(res,num,0);
        return res;
    }

    public static void process2(ArrayList<ArrayList<Integer>> res,int[] num, int i) {
        if (i == num.length) {
            ArrayList<Integer>list=new ArrayList<Integer>();
            for(int a : num){
                list.add(a);
            }
            res.add(list);
            return;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int j = i; j < num.length; j++) {
            if (!set.contains(num[j])) {
                set.add(num[j]);
                swap(num, i, j);
                process2(res, num, i + 1);
                swap(num, i, j);
            }
        }
    }

    public static void swap(int[] chs, int i, int j) {
        int tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }
}