King Of Interviews

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

Example 1:

Input: nums = [1,1,2]
Output: [[1,1,2], [1,2,1], [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

Try this Problem on your own or check similar problems:

Solution:

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        helper(nums, new ArrayList<>(), result, new boolean[nums.length]);
        return result;
    }

    private void helper(int[] nums, List<Integer> currentList, List<List<Integer>> result,boolean[] visited){
        if(currentList.size() == nums.length){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = 0; i < nums.length; ++i){
            if(!visited[i] && (i == 0 || nums[i - 1] != nums[i] || visited[i-1])){
                currentList.add(nums[i]);
                visited[i] = true;

                helper(nums, currentList, result, visited);

                currentList.remove(currentList.size() - 1);
                visited[i] = false;
            }
        }
    }
}

Time/Space Complexity:

Time Complexity: O(n*n!)
Space Complexity: O(n)

Explanation:

Combining the ideas from Permutations and from Subsets II we can easily get to this solution. Note is almost identical to the permutations where input array has no duplicates, but now we use the techniques explained in the subsets of input array with duplicates. So, we sort the input array and then only choose element if it wasn’t visited yet and it fulfills either one of the following requirements:

it’s the first element to choose
it’s different than the previous element
it’s the same as the previous element, but the previous element has also been chosen.

The rest of the solution follows the same logic as we had Permutations with the same time and space complexity.

Permutations II