Permutations II - Solution & Explanation

Problem Overview: Given an array that may contain duplicate numbers, generate every unique permutation. The challenge is avoiding duplicate permutations that arise when the same value appears multiple times in different positions.

Approach 1: Backtracking with Used Array (O(n! * n) time, O(n) space)

This approach sorts the array first, then builds permutations using backtracking. A boolean used[] array tracks which indices are already part of the current permutation. During iteration, skip an element if it is already used or if it equals the previous element and the previous element was not used in this recursion level. That condition prevents generating duplicate orderings. Each recursive step appends a number, explores deeper, then backtracks by removing it. Sorting plus the duplicate-skip rule ensures every permutation is produced exactly once.

The algorithm explores a permutation tree of depth n. Constructing each permutation takes O(n), and there can be up to n! permutations, giving O(n! * n) time complexity. Auxiliary space is O(n) for recursion and the used array (excluding output). This is the most common solution in interviews because it demonstrates clean pruning logic and understanding of permutation generation.

Approach 2: Recursive Swap with Set (O(n! * n) time, O(n) space)

This method treats the array like a permutation-in-progress and swaps elements into the current position. At recursion depth i, iterate from i to the end and swap each candidate into index i. To avoid duplicates, maintain a Set for the current recursion level that records which values have already been placed at index i. If a value has been used in this position before, skip it. After the recursive call finishes, swap the elements back to restore the original order.

The swap approach avoids maintaining a separate path array and works directly on the array. It generates permutations in-place and prevents duplicate branches using the per-level set. Time complexity remains O(n! * n) because each permutation requires copying or constructing a length-n list, and the recursion tree can grow factorially. Space complexity is O(n) for recursion depth plus the temporary set used at each level.

Recommended for interviews: Backtracking with a sorted array and a used[] check is the standard answer. It clearly shows how duplicate pruning works and is easier to reason about under pressure. The swap-with-set method is also valid and demonstrates deeper understanding of permutation generation, but interviewers typically expect the sorted backtracking approach when solving permutation problems with duplicates.