Why did this solution not work?


  • 0
    J

    this solution couldn't pass the case [-1,2,0,-1,1,0,1]. what I did was similar to declaring a hashset, just checking if the duplicate numbers have been swapped before. But I don't know why this solution doesn't work?

    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            helper(nums, 0, res);
            return res;
        }
        
        private void helper(int[] nums, int index, List<List<Integer>> res) {
            if(index == nums.length) {
                List<Integer> temp = new ArrayList<>();
                for(int j = 0; j < nums.length; j++) {
                    temp.add(nums[j]);
                }
                res.add(temp);
                return;
            }
            
            for(int i = index; i< nums.length; i++) {
                if(i > index && (nums[i] == nums[index] || nums[i] == nums[i-1])) continue;
                swap(nums, i, index);
                helper(nums, index +1, res);
                swap(nums, i, index);    
            }
    
        }
        
        private void swap(int[] nums, int a, int b){
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;   
        }
    }
    

  • 0
    P

    Per your logic after swapping the elements in bold [0,2,1,0,-1,1,-1] and enumerating all the permutations with the prefix 0,2,1,-1 , it fails to identify the fact that those permutations would be repeated if you swap these elements as well
    [0,2,1,0,-1,1,-1]

    I know that my logic incurs bit more space but this works

     public IList<IList<int>> PermuteUnique(int[] a) {
            IList<IList<int>> perms = new List<IList<int>>();
            PermuteUnique(a, 0, a.Length-1, ref perms);
            return perms;
        }
        
        private void Swap(int[] a, int x, int y)
        {
            int tmp = a[x];
            a[x] = a[y];
            a[y] = tmp;
        }
        
        private void PermuteUnique(int[] a, int lBound, int uBound, ref IList<IList<int>> perms)
        {
            if(lBound == uBound)
            {
                IList<int> cList = new List<int>(a);
                perms.Add(cList);
                return;
            }
            
            HashSet<int> hs = new HashSet<int>();
            for(int i=lBound;i<=uBound;i++)
            {
                if(!hs.Add(a[i])) continue;
                Swap(a, lBound, i);
                PermuteUnique(a, lBound+1, uBound, ref perms);
                Swap(a, lBound, i);
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.