Permutation based on swap, beat 98%


  • 0
    M
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            permute(nums, 0, res);
            return res;
        }
        
        private void permute(int[] nums, int pos, List<List<Integer>> res){
            if(pos>=nums.length){
                List<Integer> list = new ArrayList<>();
                for(int num : nums) {
                    list.add(num);
                }
                res.add(list);
                return;
            }
            for(int i=pos; i<nums.length; i++){
                if(i!=pos && (nums[i]==nums[i-1] || nums[pos]==nums[i])) continue;
                swap(nums, i, pos);
                permute(nums, pos+1, res);
            }
            for ( int i = pos; i+1 < nums.length; i++ ) {
                swap(nums, i, i+1);
            }
        }
        
        private void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

    The swapped array will keep the sorted order by for swap loop.


  • 0
    S

    Whats wrong with my soln. its passing 29/30 test cases but last one [-1,2,0,-1,1,0,1].

    class Solution {
       private void swap(int i, int j, int[] nums) {
    		int t = nums[i];
    		nums[i] = nums[j];
    		nums[j] = t;
    	}
    
    	public List<List<Integer>> permuteUnique(int[] nums) {
    		List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);
    		perrmuteUniqueHelper(nums,result,0,new ArrayList<Integer>());
    		return result;
    	}
    
    	private void perrmuteUniqueHelper(int[] nums, List<List<Integer>> result, int currentIndex,ArrayList<Integer> currentList) {
    		if(currentIndex==nums.length){
    			result.add(new ArrayList<>(currentList));
    			return;
    		}
    		for (int j = currentIndex; j < nums.length; j++) {
    			if(j!=currentIndex && (nums[j]==nums[currentIndex] || nums[j-1]==nums[j]))
    				continue;
    			swap(j,currentIndex,nums);
    			currentList.add(nums[currentIndex]);
    			perrmuteUniqueHelper(nums,result,currentIndex+1,currentList);
    			currentList.remove(currentList.size()-1);
    			swap(currentIndex,j,nums);
    		}
    	}
    }
    

Log in to reply
 

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