AlgoMaster Logo

Permutations II

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

This problem extends the standard Permutations problem (LeetCode #46), with one added complication: the input can contain duplicate values. If we generate all permutations of [1, 1, 2] without any special handling, we get six results, but [1, 1, 2] appears twice (once when we pick the first 1 first, and once when we pick the second 1 first). Since both 1s are identical, those two results are the same permutation.

The challenge is not generating permutations. It is generating them without duplicates. We need a strategy that either avoids creating duplicates in the first place or filters them out afterward. The first option does less work.

One way to avoid duplicates: sort the array first so equal values sit next to each other. During backtracking, when choosing which element to place at the current position, we can skip a value if an identical copy was already tried at this position in an earlier branch.

Key Constraints:

  • 1 <= nums.length <= 8 → The number of permutations is at most 8! = 40,320, so even generating all permutations and deduplicating afterward runs fast. Backtracking is the standard technique.
  • -10 <= nums[i] <= 10 → Only 21 distinct values are possible, so with up to 8 elements, duplicates are common. The solution must handle them correctly.

Approach 1: Brute Force (Generate All + Deduplicate)

Intuition

Ignore the duplicates entirely. Generate all n! permutations using standard backtracking, collect them into a set, and let the set discard the repeats.

A set discards equal entries automatically, so any permutation generated more than once is stored only once. The cost is wasted generation. For an input like [1, 1, 1, 1, 1, 1, 1, 1], there is only 1 unique permutation, but this generates all 8! = 40,320 of them and discards 40,319.

Algorithm

  1. Use standard backtracking to generate all permutations. Maintain a boolean array to track which indices are currently in use.
  2. At each level of recursion, try placing each unused element at the current position.
  3. When a complete permutation is formed (all positions filled), add it to a set for deduplication.
  4. After generating all permutations, convert the set back to a list of lists and return it.

Example Walkthrough

Input:

0
1
1
1
2
2
nums

We generate all 3! = 6 permutations: [1a,1b,2], [1a,2,1b], [1b,1a,2], [1b,2,1a], [2,1a,1b], [2,1b,1a]. After deduplication, only 3 unique permutations remain:

0
1
2
0
1
1
2
1
1
2
1
2
2
1
1
result

Code

This approach generates every permutation, including the duplicates, then discards the extras. The next approach skips duplicate branches before generating them.

Approach 2: Backtracking with Sorting and Pruning

Intuition

Prevent duplicates from being generated instead of removing them afterward. Sort the array so equal values are adjacent, then during backtracking, skip an element if it has the same value as the previous element and the previous element is not used in the current partial permutation.

This forces a fixed ordering among equal elements. When multiple copies of a value exist, they must be placed in the order they appear in the sorted array. Labeling two equal 1s as 1a and 1b, the rule is: never place 1b before 1a.

Algorithm

  1. Sort the input array so duplicates are adjacent.
  2. Create a boolean array used to track which elements are in the current partial permutation.
  3. Run backtracking. At each level, iterate through all elements:
    • Skip if the element is already used.
    • Skip if i > 0 and nums[i] == nums[i-1] and used[i-1] is false (the pruning rule).
    • Otherwise, mark as used, add to the current path, recurse, then backtrack.
  4. When the current path reaches length n, add a copy to the results.

Example Walkthrough

1Start: nums=[1,1,2], used=[F,F,F], current=[]
0
1
1
1
2
2
1/10

Code

The sorting approach needs an upfront sort and a pruning condition that is easy to get wrong. The next approach removes both by branching on values rather than indices.

Approach 3: Backtracking with Frequency Counter

Intuition

Instead of tracking individual array indices, count the frequency of each distinct number. During backtracking, iterate over the distinct numbers and place one of each available value at the current position.

This avoids duplicates because the algorithm never distinguishes between individual copies of the same number. With three 1s, placing a 1 means decrementing the count of 1, not selecting a specific copy. There is no sort, no used array, and the skip condition becomes a single check: branch on a value only if its remaining count is greater than zero.

Algorithm

  1. Build a frequency map counting occurrences of each distinct number.
  2. Run backtracking. At each level, iterate over the keys (distinct values) of the frequency map:
    • If the count of a value is 0, skip it.
    • Otherwise, decrement the count, add the value to the current path, recurse, then backtrack (increment count, remove from path).
  3. When the current path reaches length n, add a copy to the results.

Example Walkthrough

1Start: freq={1:2, 2:1}, current=[]
1
:
2
2
:
1
1/10

Code