Permutations II - Video Solutions

Problem Overview: You are given an integer array that may contain duplicates. The task is to return all unique permutations of the numbers. The challenge is avoiding duplicate permutations that naturally appear when identical values exist in the input array.

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

This is the most common approach used in interviews. Start by sorting the array so duplicate numbers appear next to each other. During backtracking, maintain a used[] array that tracks which indices are already included in the current permutation path. When iterating through the array, skip a number if it is the same as the previous one and the previous copy was not used in the current branch. This rule prevents generating duplicate permutations. The recursion builds permutations step by step and adds them to the result once the path length reaches n. Time complexity is O(n! * n) because there are up to n! permutations and each permutation construction costs O(n). Space complexity is O(n) for the recursion stack and used array (excluding output).

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

This approach generates permutations by swapping elements in place, similar to classic permutation generation. At each recursion level, iterate from the current index to the end and swap the chosen element into the current position. A local HashSet or set is used at each level to track which values have already been placed at that position. If a value has already been used in that level, skip it to prevent duplicate permutations. After exploring a branch, swap the elements back to restore the original array before continuing. This technique relies heavily on array manipulation and backtracking. The time complexity remains O(n! * n) because each permutation requires copying or recording the current array state, and the recursion depth is n. Space complexity is O(n) due to recursion depth and the per-level set.

Recommended for interviews: Backtracking with a used array and sorted input is the approach most interviewers expect. It clearly demonstrates how you handle duplicates while generating permutations. Starting with naive permutation generation shows baseline understanding, but adding the duplicate-skipping rule proves you understand pruning and efficient backtracking design. The swap-with-set approach is also valid but slightly less intuitive because duplicate control happens through an additional set at each recursion level.