Ac solution code


  • 0

    The basic idea is using DFS to pick up one unvisited element from the array to append to the position current.size() of 'current' array.

    To ignore duplicates: we don't put the same element to the same position

    Time complexity = O(n!)

    For position i, there're (n-i) possible numbers to put if no duplicates. So it's (n-0)(n-1)(n-2)..(n-(n-1)) = n!

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>>res = new LinkedList<List<Integer>>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        DFS(nums, new LinkedList<Integer>(), new boolean[nums.length], res);
        return res;
    }
    
    // Pick up one unvisited element from the array to append to the position current.size() of 'current' array
    void DFS(int[] nums, List<Integer>current, boolean visited[], List<List<Integer>>res) {
    	if (current.size() == nums.length) {
    		res.add(new LinkedList<Integer>(current));
    		return;
    	}    	
    	for (int i = 0; i < nums.length; i++) {
    		if (!visited[i]) {
    			visited[i] = true;
    			current.add(nums[i]);
    			DFS(nums,current, visited, res);
    			current.remove(current.size() - 1);
    			visited[i] = false; 
    			
        		while (i + 1 < nums.length && nums[i + 1] == nums[i])// Ignore duplicates: we don't put the same element to the same position
        			i++;
    		}
    	} 
    }

Log in to reply
 

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