Hope my solution will help you figure out why it is always LTE in Java Code


  • 3
    M

    My Solution is below, and I think there are two important things we need understand:

    1. When we swap the start number with the latter one, notice that if the latter number equals to the start number, skip the swap process
    2. When we iterate the numbers, we can't swap the number which is already swap with the start number, for example, the given array is [2,1,1], we swap the second '1' with '2', so next, we must skip swap the third '1' with '2'.

    Both of the two things can be easily solved by HashSet. Here is my solution.

    public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(num == null)
            return null;
        List<Integer> ori = new ArrayList<Integer>();
        for(int i : num)
            ori.add(i);
        permute(ori,0,ret);
        return ret;
    }
    
    public void permute(List<Integer> num,int start,List<List<Integer>> ret) {
        if(start == num.size() -1) {
            ret.add(new ArrayList<Integer>(num));
        } else {
            // Use hashset to store the start number, and the numbers which have already been swaped
            HashSet<Integer> hash = new HashSet<Integer>();
            hash.add(num.get(start));
            permute(num,start+1,ret);
            for(int i=start+1;i<num.size();++i) {
                if(hash.contains(num.get(i)))
                    continue;
                hash.add(num.get(i));
    
                int tmp = num.get(start);
                num.set(start,num.get(i));
                num.set(i,tmp);
    
                permute(num,start+1,ret);
    
                tmp = num.get(start);
                num.set(start,num.get(i));
                num.set(i,tmp);
            }
        }
    }
    

    }


  • 0
    N

    Same idea with you, that helps a lot, thanks!


  • 0
    Z

    Hi, I wonder why you call the "permute()" before the for loop.


  • 0
    S

    This solution also gives time out?


Log in to reply
 

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