Permutations with Duplicates

When the input contains duplicate elements, generating permutations requires extra care to avoid duplicate results.

For example, given:

[1, 1, 2]

A naive permutation algorithm would produce duplicate permutations like:

[1, 1, 2]
[1, 2, 1]
[1, 1, 2]  ← duplicate
[1, 2, 1]  ← duplicate
[2, 1, 1]
[2, 1, 1]  ← duplicate

Our goal is to generate only unique permutations.

Key Insight

To avoid duplicates:

1. Sort the input
2. Skip duplicate choices during backtracking

Sorting groups identical elements together, making it easy to detect when a choice would produce a duplicate permutation.

Strategy to Skip Duplicates

When iterating choices at a given recursion level:

• If nums[i] == nums[i - 1]
• And nums[i - 1] was not used in the current branch → skip nums[i]

This ensures each unique value is chosen once per position.

Backtracking Rules (With Duplicates)

At each step:

• Choose an unused element

• Skip duplicates only if:

  • It’s the same as the previous element
  • The previous element has not been used in this recursion path

Backtracking Template

sort(nums)
backtrack():
    if permutation complete:
        record result
        return

    for i in range(nums):
        if used[i]: continue
        if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
            continue

        choose nums[i]
        backtrack()
        undo choice

Rust Implementation

pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();

    let mut result = Vec::new();
    let mut current = Vec::new();
    let mut used = vec![false; nums.len()];

    backtrack(&nums, &mut used, &mut current, &mut result);
    result
}

fn backtrack(
    nums: &[i32],
    used: &mut Vec<bool>,
    current: &mut Vec<i32>,
    result: &mut Vec<Vec<i32>>,
) {
    if current.len() == nums.len() {
        result.push(current.clone());
        return;
    }

    for i in 0..nums.len() {
        if used[i] {
            continue;
        }

        // Skip duplicates
        if i > 0 && nums[i] == nums[i - 1] && !used[i - 1] {
            continue;
        }

        used[i] = true;
        current.push(nums[i]);

        backtrack(nums, used, current, result);

        current.pop();      // undo choice
        used[i] = false;
    }
}

Example Usage

fn main() {
    let nums = vec![1, 1, 2];
    let perms = permute_unique(nums);

    for p in perms {
        println!("{:?}", p);
    }
}

Output:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

Why the Duplicate Check Works

Consider [1, 1, 2]:

• At the same recursion level, choosing the second 1 first would produce the same permutations as choosing the first 1

• The condition !used[i - 1] ensures:

  • We only skip duplicates within the same decision level
  • We still allow valid permutations deeper in the recursion

This subtle condition is crucial.

Time and Space Complexity

Time Complexity

Where k₁, k₂, … are counts of duplicate elements.

Space Complexity

Common Mistakes

• Forgetting to sort input
• Skipping duplicates without checking used[i - 1]
• Removing valid permutations accidentally
• Treating duplicates like combinations logic

Permutations vs Permutations with Duplicates

Summary

• Duplicate elements require special handling
• Sorting + careful skipping prevents duplicates
• Backtracking logic remains mostly unchanged
• Very common interview and contest problem

Playground Links

Rust - Permutations with Duplicates