Java Recursive solution without extra space


  • 1

    This solution is inspired by @xiaohui7's solution for the permutation 1. There are mainly two changes to that solutions. First, the array need to be sorted so duplicate can be easily detected. Second, @xiaohui7 swap two elements, run the permute method recursively, and then immediately swap the previous two elements back. However, this would make break the sorted property of the remaining array. Thus, instead, I restore the element positions at the end of the functions.

    public class Solution {
        
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> permutations = new ArrayList<List<Integer>>();
            permute(nums, 0, permutations);
            return permutations;
        }
        
        public void permute(int[] nums, int begin, List<List<Integer>> permutations) {
            if ( begin == nums.length-1 ) {
                permutations.add( convertArrayToList(nums) );
            } else if ( begin < nums.length-1 ) {
                for ( int i = begin; i < nums.length; i++ ) {
                    if ( i == begin || nums[begin] != nums[i] ) {
                        swap(nums, i, begin);
                        permute(nums, begin+1, permutations);
                    }
                }
                for ( int i = begin; i+1 < nums.length; i++ ) {
                    swap(nums, i, i+1);
                }
            }
        }
        
        public void swap(int[] arr, int i, int j) {
            if ( i != j ) {
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
        
        public List<Integer> convertArrayToList(int[] nums) {
            List<Integer> list = new ArrayList<Integer>(nums.length);
            for ( int num : nums ) { list.add(num); }
            return list;
        }
    }

  • 0
    C

    Could you please explain about

    for ( int i = begin; i+1 < nums.length; i++ ) {
                    swap(nums, i, i+1);
    }

Log in to reply
 

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