47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, 0, res);
        return res;
        
    }
    // switch the current number with each of the numbers after index
    private void dfs(int[] nums, int index, List<List<Integer>> res){
        if (index == nums.length-1){
            List<Integer> list = new LinkedList<>();
            for(int num: nums){
                list.add(num);
            }
            res.add(list);
        }
        
        Set<Integer> memo = new HashSet<>();        
        for(int i=index; i<nums.length; i++){
            if (memo.contains(nums[i])) continue;
            memo.add(nums[i]);
            swap(nums, index, i);
            dfs(nums, index+1, res);
            swap(nums, index, i);
        }
    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}