Compile Ready
Module 3 · Permutation Pattern

Permutations II

MediumProblem 4 of 17 9 min read ~20 min to solve LeetCode
BacktrackingRecursionDFSPermutationSortingPruning
Asked atAmazonGoogleMicrosoftMetaApple

Problem Statement

Given an array nums that may contain duplicate values, return all unique permutations in any order.

Input

An integer array nums where equal values may appear at multiple indices.

Output

A list of unique permutations. Two permutations are the same when they contain the same values in the same order.

Constraints

  • •1 <= nums.length <= 8
  • •-10 <= nums[i] <= 10
  • •nums may contain duplicate values

Examples

Example 1

Input: 
nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Explanation: Swapping the two equal **1** values does not create a new value ordering, so only three unique permutations remain.

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]]
Explanation: With all values distinct, this reduces to the original permutation problem.

Example 3

Input: 
nums = [2,2,2]
Output: [[2,2,2]]
Explanation: All indices carry the same value, so every index ordering produces the same value ordering.

Learning Objectives

  • Sort duplicate values so equal candidates become adjacent.
  • Use **used[]** for index reuse and a separate skip rule for duplicate values.
  • Explain why the previous equal not yet used guard fixes a canonical order among equal values.
  • Generate each unique permutation once without post-processing with a set.

Intuition

Pattern Recognition

This is still the permutation placement pattern: order matters, each recursion depth fills one output position, and each index can be used once. The new signal is duplicate values. If two equal values are treated as different choices at the same depth, the recursion tree creates identical value sequences through different index identities.

Intuition

Sort the array first so equal values sit next to each other. Then enforce a canonical rule among equal values: when the previous equal value has not been used in the current prefix, do not use the later equal value yet. That means equal copies are chosen from left to right within any sibling group. We still allow the later equal value after the previous one is already in the path, because then they occupy different positions in a legitimate permutation.

Common mistakes

  • ×Skipping every duplicate value unconditionally, which prevents valid permutations like **[1,1,2]**.
  • ×Using the wrong guard **used[i - 1]** instead of **!used[i - 1]**, which skips the cases where duplicate copies should be allowed together.
  • ×Forgetting to sort first, so adjacent duplicate checks do not group equal values reliably.
  • ×Using a result set to remove duplicates after generating them, which hides the pruning idea and wastes factorial work.

Algorithm Explanation

State

Each frame carries the sorted nums, the current path, the boolean used[] array, and the shared result list. The depth is path.length. The used[] array still prevents reusing the same index, while sorting enables duplicate-aware pruning across neighbouring equal values.

Recursion tree

For sorted nums = [1,1,2], the root first chooses the 1 at index 0, then can choose the 1 at index 1 or 2, producing leaves [1,1,2] and [1,2,1]. Back at the root, the branch that tries the 1 at index 1 is pruned because the previous equal 1 at index 0 is not used. Finally, choosing 2 at the root leads to [2,1,1]. The duplicate root branch that would mirror the first 1 branch never runs.

Pruning

After sorting, skip nums[i] when i > 0, nums[i] == nums[i - 1], and used[i - 1] is false. This is the previous equal not yet used rule. It fixes the relative order of equal elements: among equal copies that are both available at the same depth, only the leftmost unused copy may start the branch. If the previous equal is already used, then the later equal copy is allowed because it is filling a later position, not competing as a sibling duplicate. This removes duplicate permutations at the source.

Algorithm

  1. Sort nums so duplicate values are adjacent.
  2. Create result, path, and used[].
  3. If path.length == nums.length, copy path into result and return.
  4. For each index i, skip it if used[i] is true.
  5. Also skip it when i > 0, nums[i] == nums[i - 1], and used[i - 1] is false.
  6. Choose nums[i], mark it used, and recurse.
  7. Unchoose by removing the last value and marking used[i] false.

Solutions

Solution: Sorted backtracking with duplicate skip

Sort first, then run the same used-array permutation template. The additional skip guard prevents a later equal value from being selected before an earlier equal value at the same decision level. That gives every value ordering one canonical index ordering.

Step-by-step

  1. Sort nums so equal values are adjacent.
  2. In the helper, copy the path when it has length n.
  3. Loop over every index at each depth, skipping indices already marked in used.
  4. For duplicates, skip index i when the previous equal index i - 1 is not currently used.
  5. Choose the candidate, recurse, and then unchoose it before testing the next candidate.
Time

O(n! * n)

Space

O(n)

In the worst case all values are distinct, so there are n! leaves and each copied permutation costs O(n). Sorting costs O(n log n) and is dominated.

Java implementation

Loading…

Dry Run

Sample input

nums = [1,1,2]. After sorting, track how the duplicate guard prunes the second root-level 1 while still allowing both 1 values inside a complete path.

depthchoicepathusedaction
0start[][F,F,F]sort to [1,1,2] and begin
01 at index 0[1][T,F,F]choose the first 1
11 at index 1[1,1][T,T,F]allowed because the previous equal is already used
22 at index 2[1,1,2][T,T,T]record [1,1,2]
12 at index 2[1,2][T,F,T]after backtracking, choose 2 before the second 1
21 at index 1[1,2,1][T,T,T]record [1,2,1]
01 at index 1[][F,F,F]skip because the previous equal index 0 is unused
02 at index 2[2][F,F,T]choose 2 as the first value
11 at index 0[2,1][T,F,T]choose the first 1 after prefix [2]
21 at index 1[2,1,1][T,T,T]record [2,1,1]

The skipped root branch is exactly the duplicate mirror of choosing index 0 first. The guard preserves valid paths with both equal values while removing sibling branches that only swap indistinguishable copies.

Interview Tips

The most important sentence is: after sorting, if the previous equal value has not been used in the current prefix, this later equal value would create a duplicate sibling branch. Make clear that used[] solves index reuse, while the sorted duplicate guard solves value-level duplication. Interviewers often test the guard by asking why !used[i - 1] is correct.

Likely follow-ups

  • How would you count unique permutations without generating them?
  • How would the solution change if values arrived one at a time and could not be sorted upfront?
  • How would you generate unique permutations in lexicographic order?
  • How would you adapt the same duplicate rule to subsets with duplicates?

Similar Problems

Permutations
MediumThe base used-array template before duplicate pruning.
Subsets II
MediumUses sorting plus a duplicate skip rule in a subset recursion tree.
Combination Sum II
MediumCombines duplicate skipping with a target-sum search.
Letter Combinations of a Phone Number
MediumAnother position-filling recursion template without duplicate values.
N-Queens
HardA richer backtracking problem where pruning removes invalid board placements.

Key Takeaways

  • Sorting groups equal values so duplicate decisions can be detected locally.
  • The guard uses **!used[i - 1]** to block later equal values only when they are sibling alternatives.
  • Equal values may still appear together in a path when the earlier copy is already used.
  • Duplicate pruning is better than generating all permutations and deduplicating afterward.
Reusable template: Duplicate-aware permutation template: sort, try every unused index, and skip a duplicate candidate when its previous equal copy is still unused.