Permutations II

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

For example, [1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution: based on Permutations, use Set to avoid duplication.

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<Integer>());
        for(int i=0; i<nums.length; i++){
            List<List<Integer>> newAns = new ArrayList<>();
            Set<String> set = new HashSet<>();
            for(List<Integer> list : ans){
                for(int pos=0; pos<=i; pos++){
                    List<Integer> newList = new ArrayList<>(list);
                    newList.add(pos, nums[i]);
                    if(set.add(newList.toString())) newAns.add(newList);
                }
            }
            ans = newAns;
        }
        return ans;
    }
}