Permutations II medium

Problem Statement

Given a collection of numbers, nums, that might contain duplicates, return all unique permutations of these numbers. You can return the answer 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]]

Steps

1. Sort the input array: Sorting the input array allows us to easily identify and skip duplicate permutations.

2. Backtracking: Use backtracking to generate all possible permutations. A backtracking algorithm recursively explores all possible arrangements of the numbers.

3. Skip Duplicates: During the backtracking process, if we encounter a number that is the same as the previous number and it's already used, we skip it to avoid generating duplicate permutations. This is because the order of identical numbers within a permutation doesn't matter.

Explanation

The core idea is to use backtracking to explore all possible arrangements of the numbers, but with a crucial addition: we skip over duplicate numbers to avoid creating duplicate permutations. Sorting the input array is key to easily detecting these duplicates. When we consider a number for a position in the permutation, we check if it's the same as the previous number and if it has been used before. If so, we skip it.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsII {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // Sort to easily handle duplicates
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentPermutation, int[] nums, boolean[] used) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // Skip duplicate numbers
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            if (!used[i]) {
                used[i] = true;
                currentPermutation.add(nums[i]);
                backtrack(result, currentPermutation, nums, used);
                currentPermutation.remove(currentPermutation.size() - 1); // Backtrack
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        PermutationsII solution = new PermutationsII();
        int[] nums1 = {1, 1, 2};
        System.out.println(solution.permuteUnique(nums1)); // [[1,1,2],[1,2,1],[2,1,1]]

        int[] nums2 = {1, 2, 3};
        System.out.println(solution.permuteUnique(nums2)); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    }
}

Complexity

• Time Complexity: O(N * N!), where N is the length of the input array. This is because we generate all permutations (N!), and for each permutation, we perform some constant-time operations. The sorting step takes O(N log N), which is dominated by the O(N!) term.

• Space Complexity: O(N), primarily due to the recursive call stack during backtracking. The space used by result and currentPermutation is also proportional to N.