0047. Permutation2

class Solution {
    // public void helper(ArrayList<Integer> num, ArrayList<Integer> cur, ArrayList<List<Integer>> res){
    //     if(num.size() == 0){
    //         res.add(cur);
    //         return;
    //     }
    //     else{
    //         for(int i = 0; i < num.size(); i++){
    //             ArrayList<Integer> newCur = new ArrayList<>(cur);
    //             newCur.add(num.get(i));
    //             ArrayList<Integer> newNum = new ArrayList<>(num);
    //             newNum.remove(num.get(i));
    //             helper(newNum, newCur, res);
    //             while(i + 1 < num.size() && num.get(i + 1) == num.get(i)) i++;
    //         }
    //     }
    // }

    // public List<List<Integer>> permuteUnique(int[] nums) {
    //     ArrayList<List<Integer>> res = new ArrayList<>();
    //     ArrayList<Integer> newCur = new ArrayList<>();
    //     ArrayList<Integer> newNum = new ArrayList<>();
    //     Arrays.sort(nums);
    //     for(int i : nums) newNum.add(i);
    //     helper(newNum, newCur, res);
    //     return res;
    // }

    public void helper(List<List<Integer>> res, List<Integer> curr, HashMap<Integer, Integer> map, int n) {
        if (curr.size() == n) {
            res.add(new ArrayList<>(curr));
        }
        else {
            for (int e : map.keySet()) {
                int sum = map.get(e);
                if (sum >= 1) {
                    curr.add(e);
                    map.put(e, sum - 1);
                    helper(res, curr, map, n);
                    curr.remove(curr.size() - 1);
                    map.put(e, sum);
                }
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int e: nums) {
            map.put(e, map.getOrDefault(e, 0) + 1);
        }
        helper(res, new ArrayList<>(), map, nums.length);
        return res;
    }
}