Permutations II

Introduction

Permutations II is a classic backtracking problem that extends the basic Permutations I problem. While Permutations I asks us to generate all possible arrangements of a set of distinct numbers, Permutations II introduces a critical constraint: the input array may contain duplicate numbers.

The Problem Statement

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

Example:

Input: nums = [1, 1, 2]

Output:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Why Standard Backtracking Fails

If we simply use the standard backtracking approach (selecting an element, adding it to the path, recursing, and backtracking), we will generate duplicate permutations. For the input [1, 1, 2], the algorithm might generate [1, 1, 2] twice because there are two '1's at different indices.

To solve this, we need a mechanism to skip selecting the same value at the same depth level if it has already been processed.

The Core Strategy: Sorting + Pruning

The most efficient and intuitive way to solve Permutations II involves two main steps:

1. Sort the Input Array: Sorting groups identical numbers together. This allows us to easily check if the current number is a duplicate of the previous one.
2. Use a used Array: This boolean array tracks which indices have been included in the current path (the current permutation being constructed).
3. Pruning Duplicates: Before selecting a number at index i, check if it is a duplicate of the previous number (nums[i] == nums[i-1]). If it is, we must ensure we are not skipping a number that was just used in the current path.

The Duplicate Skipping Logic

The critical condition to prevent duplicates is:

if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
  continue;
}

Why !used[i - 1]?

• If used[i - 1] is true: The previous duplicate number was used in the current permutation. This means we are allowed to use the current duplicate number to form the next permutation (e.g., moving the second '1' to the end).
• If used[i - 1] is false: The previous duplicate number was not used in the current permutation. If we use the current duplicate number now, we would create a permutation that is identical to one generated earlier when we processed the previous duplicate number. Therefore, we skip it.

Implementation

Here is the complete TypeScript implementation using the used array approach.

function permuteUnique(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);

  // Step 1: Sort the array to group duplicates
  nums.sort((a, b) => a - b);

  function backtrack() {
    // Base case: if the path length equals the input length, we have a complete permutation
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      // Step 2: Skip duplicates
      // If the current number is the same as the previous number,
      // AND the previous number was NOT used in the current path,
      // then we skip the current number to avoid duplicate permutations.
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue;
      }

      // Step 3: Skip if already used
      if (used[i]) {
        continue;
      }

      // Choose
      used[i] = true;
      path.push(nums[i]);

      // Explore
      backtrack();

      // Un-choose (Backtrack)
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return result;
}

Complexity Analysis

Time Complexity: O(N * N!)

• N: The number of elements in the input array.
• N!: In the worst case (all distinct elements), there are N! permutations.
• N: For each permutation, we copy the path into the result array, which takes O(N) time.

Space Complexity: O(N)

• O(N): The recursion stack depth can go up to N.
• O(N): The used array stores N booleans.
• O(N!): The output storage itself, which is required by the problem.

Common Pitfalls & Debugging

1. Forgetting to Sort: If you don't sort the array first, the duplicate check nums[i] === nums[i-1] will not work correctly because duplicates will be scattered throughout the array.
2. Incorrect Skip Condition: The most common mistake is using used[i] instead of !used[i-1] in the condition.

• Wrong: if (i > 0 && nums[i] === nums[i - 1] && used[i]) -> This skips the second occurrence of a duplicate even if the first one was used, which is incorrect.

1. Modifying the Input Array: Ensure you don't modify the original nums array (e.g., by removing elements) unless you make a deep copy, as this can affect the used array logic or subsequent calls.

Comparison: Permutations I vs. Permutations II

| Feature | Permutations I | Permutations II |

| :--- | :--- | :--- |

| Input | Distinct numbers | May contain duplicates |

| Output | All unique permutations | All unique permutations |

| Key Logic | Standard backtracking | Sorting + Duplicate Pruning |

| Optimization | None required | used array pruning is crucial |

Real-World Applications

1. Combinatorial Generation: Generating all valid configurations of a system with identical components (e.g., arranging a deck of cards where suits are identical, or arranging a password with repeated characters).
2. Scheduling: Finding all possible schedules where tasks with the same priority can be swapped without changing the outcome.
3. Game AI: Generating all possible moves in a game state where some moves are functionally identical (e.g., moving a pawn forward two squares vs. one square in chess, depending on board state).