Permutations II medium

Problem Statement

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

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 helps us easily identify and skip duplicate permutations.

2. Backtracking: Use backtracking to generate all permutations.

3. Skip duplicates: During backtracking, if a number is the same as the previous number and the previous number hasn't been used, skip it to avoid generating duplicate permutations.

4. Base Case: When the current permutation's length equals the length of the input array, add it to the result.

Explanation

The core idea is to use backtracking with a crucial addition to handle duplicates. Sorting the input array allows us to easily compare adjacent elements. If we encounter a duplicate number and its previous instance hasn't been used in the current permutation, we skip it. This ensures that we only generate unique permutations. The backtracking process systematically explores all possible arrangements of the numbers.

Code

function permuteUnique(nums: number[]): number[][] {
    const result: number[][] = [];
    nums.sort((a, b) => a - b); // Sort for duplicate handling
    const n = nums.length;
    const used: boolean[] = new Array(n).fill(false);
    const currentPermutation: number[] = [];

    function backtrack() {
        if (currentPermutation.length === n) {
            result.push([...currentPermutation]); // Add a copy to avoid modification
            return;
        }

        for (let i = 0; i < n; i++) {
            if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) {
                continue; // Skip if used or duplicate and previous not used
            }
            used[i] = true;
            currentPermutation.push(nums[i]);
            backtrack();
            currentPermutation.pop();
            used[i] = false;
        }
    }

    backtrack();
    return result;
}

Complexity

• Time Complexity: O(N * N!), where N is the length of the input array. Generating all permutations takes N! time, and for each permutation, we perform operations that take O(N) time (e.g., copying the array).

• Space Complexity: O(N), primarily due to the recursive call stack during backtracking and the used array. The result array can also take up O(N * N!) space in the worst case, but this is dependent on the number of unique permutations. In practice, the space used by the result array is often much smaller than the theoretical maximum.