I think this could be a right answer, however time limit exceed.


  • 0
    W
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        boolean[] visited=new boolean[nums.length];
        helper(result,visited,nums,new ArrayList<Integer>());
        return result;
    }
    
    private void helper(List<List<Integer>> result, boolean[] visited, int[] nums, List<Integer> list){
        if(list.size()==nums.length){
        	result.add(list);
        	return;
        }
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                List<Integer> newList=new ArrayList<Integer>(list);
                newList.add(nums[i]);
                visited[i]=true;
                helper(result,visited,nums,newList);
                visited[i]=false;
            }
        }
    }
    

    After changed to https://leetcode.com/discuss/41373/standard-dfs-java-solution , the code would be accepted.


  • 0
    Q

    the problem is that you do not check the repeats, sorry for misunderstanding your code.
    I have made some changes on your code.

    public class Solution {
            public List<List<Integer>> permuteUnique(int[] nums) {
                List<List<Integer>> result=new ArrayList<>();
                Arrays.sort(nums);
                boolean[] visited=new boolean[nums.length];
                helper(result,visited,nums,new ArrayList<Integer>());
                return result;
            }
            
            private void helper(List<List<Integer>> result, boolean[] visited, int[] nums, List<Integer> list){
                if(list.size()==nums.length){
                    result.add(list);
                    return;
                }
                for(int i=0;i<nums.length;i++){
                    if(!visited[i]){
                        List<Integer> newList=new ArrayList<Integer>(list);
                        newList.add(nums[i]);
                        visited[i]=true;
                        helper(result,visited,nums,newList);
                        visited[i]=false;
                        
                        while (i < nums.length - 1 && nums[i] == nums[i+1])  i++;
                    }
                }
            }
        }

  • 0
    W

    Actually my accepted code also create as many lists,but no TLE or MLE.


  • 0
    Q

    I have attached the revised code in the answer, thanks.


  • 0
    W

    Thank you. However. I don't understand what do you mean by "only contains one element". Every time I create a new list, " ArrayList<Integer>(list)" means it already contains the elements in the original list. I've tried this method in IDE and it works well.


  • 0
    W

    Right, it would be much faster after checking repeats.


Log in to reply
 

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