Java Recursive Solution with Minimal Extra Space


  • 6
    H

    The idea is to directly modify the order of original array using a swap method instead of creating new list saving the results of every recursive call.

    public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        List<List<Integer>> result = new ArrayList();
        if(nums.length==0) return result;
        backTrack(nums, result, 0, nums.length-1);
        return result;
        
    }
    
    public void backTrack(int[] nums, List<List<Integer>> result, int begin, int end){
        if(begin>end){
            //changing int[] to arraylist and save into final result list
            result.add(new ArrayList<Integer>() {{ for (int i : nums) add(i); }});
        }
        
        else{
            for(int i=begin; i<=end; i++){
               
                if(!isDuplicate(nums, begin, i)){
                    swap(nums,i,begin);
                    backTrack(nums, result, begin+1, end); 
                    swap(nums,i,begin);
                }
                
            }
        
        }
        
    }
    
    //check whether the current number has appeared in the subarray. if same number appears, we do not need to move this number again
    
    public boolean isDuplicate(int[] nums, int begin, int i){
        for(int a=begin; a<i; a++){
            if(nums[a]==nums[i]){
                return true;
            }
        }
        return false;
    }
    
    public void swap(int[] nums, int i, int j){
        int buf = nums[i];
        nums[i] = nums[j];
        nums[j] = buf;
    }
    

    }


Log in to reply
 

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