TLE problem, I failed on this [-1,2,-1,2,1,-1,2,1] test. But pass in my Netbeans


  • 0
    S
    import java.util.HashMap;
    public class Solution {
        public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> arr = new ArrayList<Integer>();
            if(num.length == 0)
            return result;
            int cur = 0;
            int [] used = new int[num.length];
            inputNum(used, num, arr, result);
            HashMap map = new HashMap();
            //remove duplicate
            for(int j=0; j<result.size();j++)
            {
               if(!map.containsValue(result.get(j)))
                {
                    map.put(j,result.get(j));
                }
                else
                {
                    result.remove(j);
                    j--;
                }
            }
        return result;
    }
    
        //transfer array to linked list
    public void inputNum(int [] used, int [] num, ArrayList<Integer> arr, 
                ArrayList<ArrayList<Integer>> result)
        {
            if(arr.size() == num.length)
            {
                ArrayList<Integer> temp = new ArrayList<Integer>(arr);
                result.add(temp);
                return;
            }
            for(int i=0; i<num.length; i++)
            {
                if(used[i] == 0)
                {
                    used[i] = 1;
                    arr.add(num[i]);
                    inputNum(used, num, arr, result);
                    used[i] = 0;
                    arr.remove(arr.size()-1);
                }
            }
        }
    }
    

    My question is I can do [-1,2,-1,2,1,-1,2,1] test well in Netbeans, but failed here. Anyone can help me?


  • 0
    K

    I had the same problem and found that when removing duplicate in each recursive procedure instead of in the end, the problem could be solved.


  • 0
    E

    Thank you for your solution.


Log in to reply
 

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