Java Solution using the Dictionary Order


  • 0
    N
     private List<List<Integer>> result = new LinkedList<List<Integer>>();
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
    	    addResult(nums);
    		while(nextPermutation(nums)){
    		}
    		return result;
        }
        
        private boolean nextPermutation(int[] nums){
            int i = findNextAccendingIndex(nums);
            if(i==-1){
                return false;
            }
            for(int j = nums.length-1;j>i;j--){
              //make it to be the next smallest permutation
                if(nums[j]>nums[i]){
                    swap(nums,i,j);
                    reverse(nums,i+1,nums.length-1);
                    addResult(nums);
                    break;
                }
            }
            return true;
        }
        
        private int findNextAccendingIndex(int[] nums){
            for(int i = nums.length-2;i>=0;i--){
                if(nums[i]<nums[i+1]){
                    return i;
                }
            }
            return -1;
        }
        
        
        private void reverse(int[] A, int left, int right){
    		while(left<right){
    			swap(A, left, right);
    			left++;
    			right--;
    		}
    	}
        private void addResult(int[] nums){
            List<Integer> list = new ArrayList<Integer>(nums.length);
            for(int i:nums){
                list.add(i);
            }
            result.add(list);
        }
        
        private void swap(int[] nums,int i,int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

Log in to reply
 

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