java solution, very easy solution with explanations.


  • 1
    N

    Firstly, when we get the question, we can see that using backtrack is the best idea. The difficulty is how to solve problem of repetition.
    Here is problem:
    when we have [1, 2, 3] and we wanna put a 3 inside, we will have:
    [1,2,3,3], [1,3,2,3], [3,1,2,3], //1,2,3
    [1,3,2,3], [1,3,3,2], [3,1,3,2], //1,3,2
    [2,1,3,3], [2,3,1,3], [3,2,1,3], //2,1,3
    [2,3,1,3], [2,3,3,1], [3,2,3,1], //2,3,1
    [3,1,2,3], [3,1,3,2], [3,3,1,2], //3,1,2
    [3,2,1,3], [3,2,3,1], [3,3,2,1]. //3,2,1
    Except for those bold arrays, we encountered the problem.(actually, there is also problem in bold arrays, but happened in the same row) But when you look into those repetition you can find out the key of the problem --- you do not have to re-add 3 to array before the previous 3.

    Sorry, poor English expression.

        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums.length == 0)    return res;
            backtrack(res, new ArrayList<Integer>(), 0, nums);
            return res;
        }
        
        private void backtrack(List<List<Integer>> res, List<Integer> temp, int pos, int[] nums){
            if(pos == nums.length){
                res.add(temp);
                return ;
            }
            
            int k = 0;
            for(int j=0;j<temp.size();j++){
                if(temp.get(j) == nums[pos])    k = j+1;    
            }
            for(int j=k;j<=temp.size();j++){
                temp.add(j, nums[pos]);
                backtrack(res, new ArrayList<>(temp), pos+1, nums);
                temp.remove(j);
            }
            
            return ;
        }
    }
    

  • 0
    N

    Sorry about the code area.

    public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if(nums.length == 0)    return res;
            Arrays.sort(nums);
            backtrack(res, new ArrayList<Integer>(), 0, nums);
            return res;
        }
        
        private void backtrack(List<List<Integer>> res, List<Integer> temp, int pos, int[] nums){
            if(pos == nums.length){
                res.add(temp);
                return ;
            }
            
            int k = 0;
            for(int j=0;j<temp.size();j++){
                if(temp.get(j) == nums[pos])    k = j+1;    
            }
            for(int j=k;j<=temp.size();j++){
                temp.add(j, nums[pos]);
                backtrack(res, new ArrayList<>(temp), pos+1, nums);
                temp.remove(j);
            }
            
            return ;
        }
    

Log in to reply
 

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