Really easy Java solution, much easier than the solutions with very high vote


  • 114

    Use an extra boolean array " boolean[] used" to indicate whether the value is added to list.

    Sort the array "int[] nums" to make sure we can skip the same value.

    when a number has the same value with its previous, we can use this number only if his previous is used

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(nums==null || nums.length==0) return res;
            boolean[] used = new boolean[nums.length];
            List<Integer> list = new ArrayList<Integer>();
            Arrays.sort(nums);
            dfs(nums, used, list, res);
            return res;
        }
    
        public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
            if(list.size()==nums.length){
                res.add(new ArrayList<Integer>(list));
                return;
            }
            for(int i=0;i<nums.length;i++){
                if(used[i]) continue;
                if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
                used[i]=true;
                list.add(nums[i]);
                dfs(nums,used,list,res);
                used[i]=false;
                list.remove(list.size()-1);
            }
        }
    }

  • 0
    Y

    good solution, but I don't think the pos is used in your code.


  • 1
    D

    I think it runs a bit faster if you use an int array instead of ArrayList to store the current permutation.
    e.g.
    Instead of:

    list.add(nums[i]);   
    ...
    list.remove(list.size()-1);  
    

    Take advantage of the "pos" variable. So we can do:

    list[pos] = nums[i];
    

    This way there is no need to grow and shrink the list.

    Lastly it is only a couple of lines to go from an int[] to ArrayList to add it to the result ArrayList.


  • 0

    You are right. If we use int array it will become faster.
    But is there an easier way to convert int array to a list of Integers?


  • 1
    Y

    I don't think it worth the effort the use an int array and then convert back to list, since you will need to copy each int to the new list. If you are working on the problem in an interview and get to choose the result type, you can use a List<int[]> instead, but for this specific design, I would think directly use a list is easier.


  • 0

    Right, there is no need to use variable pos. I removed it.


  • 3
    J

    Can someone explain this line:
    if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
    Why does it work if we have for example 3 duplicates in a row? We check only the one previously


  • 0
    Y

    For duplicate more than 3, if(used[i]) continue; takes care of it, since it will be set as used.


  • 1
    K

    well, now your solution becomes one of those with high votes~


  • 6

    Well, advertising is very important.


  • 1
    N

    What would be time complexity for this solution ?


  • 0
    L

    Very good solution. Better time complexity for using pruning to duplicate elements. Thanks!


  • 1
    J

    Time complexity is very high. it is O(n^n).


  • 7
    5

    Is this "if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;" should be "if(i>0 &&nums[i-1]==nums[i] && used[i-1]) continue;" ?


  • 0
    L

    I got similar thinking as yours but stuck due to missing of "!used[i-1]" part, your solution really enlightened me. Thank you!

    Following is C++ solution, generally the same thing as yours.

    class Solution {
    public:
        /**
         * @param nums: A list of integers.
         * @return: A list of unique permutations.
         */
        vector<vector<int> > permuteUnique(vector<int> &nums) {
            // write your code here
            vector<vector<int> > res;
            if (nums.empty()) return res;
            vector<bool> visited(nums.size(),false);
            vector<int> vtmp;
            sort(nums.begin(), nums.end());
            helper(nums, visited, vtmp, res);
            return res;
        }
        
        void helper(vector<int> &nums, vector<bool> &visited, vector<int> vtmp, 
                 vector<vector<int> > &res) {
            if (vtmp.size() == nums.size()) {
                res.push_back(vtmp);
                return;
            }
            
            for (int i(0); i<nums.size(); i++) {
                if (visited[i] || (i && nums[i] == nums[i-1] && !visited[i-1]))
                    continue;
                vtmp.push_back(nums[i]);
                visited[i]=true;
                helper(nums, visited, vtmp, res);
                visited[i]=false;
                vtmp.pop_back();
            }
        }
    };
    

  • 4
    T

    @UpTheHell Can you explain the use of !used[i-1] in the 2nd if condition in the for loop inside dfs() ?

    Thanks very much


  • 21

    @thalaivva
    I think both

    if(i > 0 && nums[i] == nums[i - 1] && !use[i - 1]) continue;
    

    and

    if(i > 0 && nums[i] == nums[i - 1] && use[i - 1]) continue;
    

    works. It's weird.

    I will try to explain it. Suppose during the ith loop, we have two consecutively same numbers, aka nums[i - 1] and nums[i]. If we add nums[i - 1] to the current list during the (i - 1)th loop and add nums[i] during the ith loop, the list will be the unique one in the result. Now lets move on. During the (i -1)th loop, if we ignore nums[i - 1] and add num[i] to the current list, since nums[i - 1] is not added thus used[i - 1] is false, plus nums[i] == nums[i - 1], hence the if-else limitation should be coded like the first one.

    But I also did not figure out why the first one also got accepted. Still, hope my explanation can be inspiring.


  • 0
    W

    said in Really easy Java solution, much easier than the solutions with very high vote:

        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
    

    why do you need to create a new list using the current list?


  • 0

    @whitecatgsd If we add the list directly into result, it will change later because list will be modified many times. So we add its copy into result.


  • 3
    G

    Another option to avoid duplicate num without sorting 'int[] nums' first, is to utilize a HashSet to track what numbers are used before, if we've used that number then skip it

    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            if(nums != null || nums.length != 0)
                permutationHelper(nums, new int[nums.length], new ArrayList<Integer>());
    		return unique_perms;
        }
        
        List<List<Integer>> unique_perms = new ArrayList<List<Integer>>();
    
        void permutationHelper(int[] nums, int[] numsVisited, List<Integer> result){
    		
    		if(result.size() == nums.length){
    			unique_perms.add(new ArrayList<Integer>(result));
    			return;
    		}
    		
    		
    		HashSet<Integer> existingNums = new HashSet<Integer>();
    		for(int i = 0; i < nums.length; i++){
    		    
    		    //if this num was visited before then skip
    			if(numsVisited[i] == 1) continue;
    			
    			//if we use this num before then skip it.
    			if(existingNums.contains(nums[i]))
    				continue;
    			else
    				existingNums.add(nums[i]);
    			
    			result.add(nums[i]);
    			numsVisited[i] = 1;
    			
    			permutationHelper(nums, numsVisited, result);
    			
    			result.remove(result.size()-1);
    			numsVisited[i] = 0;
    		}
    	}
    }
    

Log in to reply
 

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