Leetcode — 47. Permutations II

The link to the problem: https://leetcode.com/problems/permutations-ii/

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

This problem is the transformation of 46. Permutations I. I would like to first mention how to do 46, then show how we can simply add some conditions to solve this problem 47.

In this problem 46. Permutations I, all the numbers in the array are non-duplicates. What we can do here is using backtracking to solve the problem.

⚠️ I think I have a nice explanation and clear steps of how we use backtracking to find all the combinations in this story: Leetcode — 39. Combination Sum

The below graph describing how we output all the permutations of the given non-duplicated array. I use an example when the input array is [10,20,30] to illustrate the backtracking approach.

Use Backtracking to find all permutations for input [10,20,30]

Unlike finding combinations, we will always have three choices (i.e., the length of the input array) for each node when finding the permutations because the order of the elements matters.
The reason why it is allowed for us to eliminate the choices that after the current position when finding the combinations is because we consider [10,20,30] and [20,10,30] are the same.

We will use an array visited for recording whether the position has been visited or not. If the array shows that the current choice has been visited, it means the current path is a dead-end, and we will undo the choice and choose other possible choices.

Below is the 1ms code that beats 93% for problem 46:

public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        helper(rst,nums,new boolean[nums.length],new ArrayList<>());
        return rst;
    }
    public void helper(List<List<Integer>> rst, int[] nums, boolean[] visited, List<Integer> inner){
        if(inner.size()==nums.length)
        {
            rst.add(new ArrayList<>(inner));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(visited[i]) //skip the choice if it is dead-end
                continue;
            inner.add(nums[i]); //select a choice
            visited[i] = true; //change the state since we choose it
            helper(rst,nums,visited,inner);
            inner.remove(inner.size()-1); //undo the choice
            visited[i] = false; //also recover the state since we undo
        }
    }

If we try to use the previous code to find the permutations when the input array = [1,2,2], what we will get is: [[1,1,2],[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]] while the answer should be only: [[1,1,2],[1,2,1],[2,1,1]].

How to prevent the duplicated inner list problem?

The easiest way is to check if the result list contains the inner list before adding it to the result list. This works but the time complexity will be high since we cannot stop the unnecessary paths properly.

The other way is to add one more condition before we try to select the current choice — we check if the number of the current position is the same as its previous position’s number. If yes, make sure the previous position has been traversed.

For example, if we have an input [1,1,2], and we didn’t add any condition, the backtracking graph will be like this:

Use Backtracking to find all permutations for input [1,1,2] ( before adding the invalid check condition)

We can see that the parts in yellow shadows and green shadows are actually duplicated. They represents the same route and choices. The only difference is that the permutations in yellow shadows will list the first 1 before the second 1 and vice versa in the green shadows.
i.e., we actually do not care about the order of duplicated 1s.
For example, if the first 1 looks like 1 and the other one looks like 1'.
There is no difference if we get a result that looks like [1,1',2] and [1',1,2] or a result looks like [1,2,1'] and [1',2,1]

That is to say, we should make a rule to make sure that we won’t consider [1,1',2] and [1',1,2] are different permutations.

The rule we make is, we DO NOT ALLOW 1' APPEARS BEFORE 1. We only accept the permutations that 1 always appears before 1'.

⚠️If there are 3 1s, looks like 1, 1', and 1'’, then the rules are still the same, 1 should always appear before 1' and 1'’, and 1' should always appear before 1'’.

That’s why we need to make sure visited[i-1] is true if we want to choose visited[i] when nums[i] equals to nums[i-1].

Use Backtracking to find all permutations for input [1,1,2] ( after adding the invalid check condition)

Originally, if we simply just check if the result list contains the same inner list before adding the inner list into the result list, it will take 241ms to run the code.
Now with the conditions we added, the codes eliminated some unnecessary paths and it now only takes 1ms to run the code:

public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        Arrays.sort(nums);
        helper(rst,nums, new ArrayList<>(), new boolean[nums.length]);
        return rst;
    }
    public void helper(List<List<Integer>> rst, int[] nums, List<Integer> inner, boolean[] visited){
        if(inner.size()==nums.length)
        {
            rst.add(new ArrayList<>(inner));
            return;
        }
        for(int i=0;i<visited.length;i++)
        {
            if(visited[i])
                continue;
            if(i!=0 && nums[i]==nums[i-1] && !visited[i-1])
                continue;
            visited[i] = true;
            inner.add(nums[i]);
            helper(rst,nums,inner,visited);
            inner.remove(inner.size()-1);
            visited[i] = false;
        }
    }

⚠️It is also important to sort the input array first to ensure the duplicated numbers are gathered.

The time complexity and space complexity are exponential since we need to find all the possible permutations.