// @Title: 全排列 II (Permutations II)
// @Author: qisiii
// @Date: 2024-09-22 00:23:32
// @Runtime: 2 ms
// @Memory: 44.2 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] color=new boolean[nums.length];
        dfs(result, new ArrayList<>(), nums,color);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums,boolean[] color) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }
        HashSet<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            //选过了
            if(color[i]){
                continue;
            }
            //同轮次中已经处理过这种情况了
            if(set.contains(nums[i])){
                continue;
            }else{
                set.add(nums[i]);
            }
            list.add(nums[i]);
            color[i]=true;
            dfs(result, list, nums,color);
            list.remove(list.size() - 1);
            color[i]=false;
        }

    }
}

// @Title: 全排列 II (Permutations II)
// @Author: qisiii
// @Date: 2024-05-10 21:04:47
// @Runtime: 4 ms
// @Memory: 44.2 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<Integer> numList = new ArrayList<>();
        for (int i : nums) {
            numList.add(i);
        }
        return permute(numList);
    }

    public List<List<Integer>> permute(List<Integer> nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.size() <= 1) {
            result.add(new ArrayList<>(nums));
            return result;
        }
        for (int j=0;j<nums.size();j++) {
            if(j!=0&&nums.get(j)==nums.get(j-1)){
                continue;
            }
            Integer i=nums.get(j);
            List<Integer> temp = new ArrayList<>(nums);
            temp.remove(i);
            List<List<Integer>> tempList = permute(temp);
            for (List<Integer> tl : tempList) {
                tl.add(0, i);
            }
            result.addAll(tempList);
        }
        return result;
    }
}

// @Title: 全排列 II (Permutations II)
// @Author: qisiii
// @Date: 2024-09-20 00:09:44
// @Runtime: 2 ms
// @Memory: 44.5 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        boolean[] color=new boolean[nums.length];
        dfs(result, new ArrayList<>(), nums,color);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] nums,boolean[] color) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }
        HashSet<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            //选过了
            if(color[i]){
                continue;
            }
            //同轮次中已经处理过这种情况了
            if(set.contains(nums[i])){
                continue;
            }else{
                set.add(nums[i]);
            }
            list.add(nums[i]);
            color[i]=true;
            dfs(result, list, nums,color);
            list.remove(list.size() - 1);
            color[i]=false;
        }

    }
}