Permutations with Duplicates

Hello! In our last lesson, we explored how to generate every possible permutation of a list of distinct elements using backtracking. We looked at two powerful patterns: one using a used array to track choices, and another using in-place swapping to save space. We concluded with a preview of a new challenge: what happens when the input list contains duplicates?

Today, we will tackle that problem head-on. This lesson is designed to help you modify the permutation generation logic to handle duplicates and avoid duplicate results. Given an input like [1, 2, 2], our goal is to produce only the unique arrangements: [[1,2,2], [2,1,2], [2,2,1]]. We'll explore two elegant and efficient patterns that prune the backtracking search tree, preventing duplicate permutations from ever being generated.

The Problem with Duplicates

Let's revisit the used array approach from the previous lesson. If our input is nums = [1, 2, 2], how does the basic algorithm go wrong? For clarity, let's think of the input as [1, 2a, 2b]. The algorithm would generate paths like:

• [1, 2a, 2b]
• [1, 2b, 2a]

When we add these to our results list, they both become [1, 2, 2], creating a duplicate. The fundamental issue is that our simple used array, which tracks elements by their index, can't distinguish that choosing 2a first and 2b second is, for the final result, the same as choosing 2b first and 2a second.

A naive fix might be to generate all permutations (including duplicates) and then filter them using a hash set. This works, but it's inefficient. We would be doing a lot of redundant work exploring identical branches of our decision tree. A much better approach is to be smarter and "prune" these redundant branches before we traverse them.

The image below illustrates the decision tree for [1, 2, 2] where these redundant branches (marked with an X) are pruned. This is our goal: to build a backtracking algorithm that only explores the necessary paths.

This decision tree for the input [1, 2, 2] shows how certain branches are skipped (X) to avoid generating duplicate permutations. For example, after starting a permutation with the 2 at index 1, the algorithm skips starting another permutation with the 2 at index 2 at the same decision level.

Method 1: Backtracking with a Frequency Map

One of the most intuitive ways to handle duplicates is to change how we view our choices. Instead of iterating through the input array [1, 2, 2], we can first count the frequency of each number: we have two 1s and one 2.

So, at any given step, our choices are not based on indices, but on the unique numbers available.

• For the first position, our choices are 1 or 2.
• If we choose 1, we now have one 1 and one 2 left.
• If we choose 2, we now have two 1s left.

This logic completely sidesteps the issue of duplicate values by thinking in terms of counts. We can implement this by first building a hash map (or a frequency counter) of the numbers in the input array. Then, our recursive function will iterate through the keys of this map.

The NeetCode video below provides an excellent whiteboard explanation of this exact strategy.

The algorithm using a frequency map is as follows:

1. Build a Frequency Map: Create a hash map that maps each unique number in nums to its count. For [1, 1, 2], this would be {1: 2, 2: 1}.
2. Base Case: In the recursive function, if the current permutation's length equals the original nums array's length, we have a complete unique permutation. Add it to the results and return.
3. Recursive Step: Iterate through the unique numbers (the keys) in the frequency map.
4. Choice & Constraint: For each number n, if its count in the map is greater than 0:
   • Add n to the current permutation.
   • Decrement its count in the map: count[n]--.
   • Make the recursive call to fill the next position.
   • Backtrack: Remove n from the current permutation and restore its count in the map: count[n]++.

This method is elegant because the source of choices (the keys of the map) is already de-duplicated.

Method 2: Sort and Skip

An alternative and very common pattern involves making a small but powerful modification to the used array approach from the previous lesson. This method requires two key steps:

1. Sort the input array: This is crucial because it places all duplicate elements next to each other. [2, 1, 2] becomes [1, 2, 2].
2. Add a skip condition: During backtracking, when we are considering which element nums[i] to pick next, we add a special rule:

If the current element nums[i] is the same as the previous element nums[i-1], and we have not used the previous element (!used[i-1]) in this path, then we skip the current element nums[i].

Let's break down the intuition for this rule: if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

When the backtracking algorithm is deciding which element to place at a certain position, it iterates through the sorted nums array. Let's say it encounters two adjacent 2s.

• It first tries placing the first 2 and recursively explores all permutations that follow.
• After backtracking, it considers placing the second 2 in that same position. The condition !used[i-1] will be true, because we have backtracked from using the first 2.
• The rule says: "Don't start a new path with this second 2 if the path with the first 2 was not taken." This effectively enforces a fixed order for picking duplicates, pruning all redundant branches and ensuring that permutations like [1, 2a, 2b] and [1, 2b, 2a] are not both generated.

The AlgoMonster and NeetCode articles below provide excellent, detailed explanations of this sort-and-skip approach.

The NeetCode article also offers a very concise summary of this method alongside other approaches.

Comparing the Methods

You now have two robust patterns for handling permutations with duplicates:

• Frequency Map:

  • Pros: Very intuitive, as it directly models picking from a bag of unique items with counts. Does not require sorting the input.
  • Cons: Requires O(k) extra space for the hash map, where k is the number of unique elements.

• Sort and Skip:

  • Pros: Very common interview pattern that builds on the standard permutation algorithm. Space-efficient, as it only needs the O(n) used array besides the recursion stack.
  • Cons: Requires an initial O(n log n) sort. The skip condition, while powerful, can be tricky to reason about and remember under pressure.

Both are excellent, efficient solutions. Having both in your toolkit allows you to choose the one that feels more natural to you or better fits a specific problem variation.

Conclusion

In this lesson, we leveled up our backtracking skills by tackling the challenge of duplicates in permutation problems. We moved beyond naive filtering and learned how to build smarter algorithms that prune the search space.

Key Takeaways:

• Generating permutations for a set with duplicates using a basic backtracking algorithm will produce redundant results.
• Frequency Map Pattern: By first counting element frequencies, you can structure your backtracking to choose from unique elements, naturally avoiding duplicate paths.
• Sort-and-Skip Pattern: By sorting the input and adding a specific condition (if (i > 0 && nums[i] == nums[i-1] && !used[i-1])), you can prune branches that would result from picking duplicates in a different order.
• Both methods are vastly more efficient than generating all permutations and filtering with a hash set.

In our next and final lesson of this module, we will step back from implementation details and focus on a crucial aspect of algorithm analysis: how to estimate the time complexity of the backtracking solutions we've developed for subsets, combinations, and permutations.