Permutations & Combinations - Learning Module

Loading content...

0/276

Handling Duplicates

The Duplicate Dilemma

All our previous algorithms assumed distinct elements. But what happens when the input contains duplicates? Consider generating permutations of [1, 1, 2]. A naive algorithm would produce:

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

Notice the duplicates! Each permutation appears twice because swapping the two 1's produces the same arrangement. For n elements with some repeated, the naive approach generates duplicate outputs—wasting computation and potentially causing incorrect behavior in applications.

The multiset permutation problem asks: how many distinct arrangements exist, and how do we generate each exactly once? This is a fundamental problem in combinatorics with applications in anagram generation, scheduling identical tasks, and many optimization problems.

This page explores the mathematical foundations of multiset permutations and combinations, multiple algorithmic strategies for avoiding duplicates, and robust implementation techniques that work correctly and efficiently.

What You Will Master

By the end of this page, you will understand:

• The mathematics of multiset permutations and combinations • Why naive algorithms produce duplicates • Three strategies: post-filtering, visited sets, and sorted-skip • The elegant 'sorted-skip' technique that avoids duplicates during generation • How to extend these techniques to combinations with duplicates • Complexity analysis and practical implementation guidelines

Mathematical Foundations: Multiset Counting

A multiset is like a set but allows repeated elements. For example, {1, 1, 2, 3, 3, 3} is a multiset where 1 appears twice, 2 once, and 3 three times. When counting arrangements of a multiset, identical elements are interchangeable—swapping them produces the same arrangement.

Multiset Permutation Formula:

For a multiset with n elements total, where element types appear with frequencies n₁, n₂, ..., nₖ (where n₁ + n₂ + ... + nₖ = n), the number of distinct permutations is:

n! / (n₁! × n₂! × ... × nₖ!)

Intuition:

Start with n! (all permutations if elements were distinct). Each group of nᵢ identical elements can be internally rearranged in nᵢ! ways without changing the visible arrangement. Dividing by each nᵢ! removes these phantom duplicates.

Multiset Permutation Examples
Multiset	Frequencies	Formula	Count
{A, A, B}	A:2, B:1	3! / (2! × 1!)	3
{1, 1, 2, 2}	1:2, 2:2	4! / (2! × 2!)	6
{a, a, a, b, b}	a:3, b:2	5! / (3! × 2!)	10
MISSISSIPPI	M:1, I:4, S:4, P:2	11! / (1! × 4! × 4! × 2!)	34,650
{1, 2, 3, 4, 5}	all:1	5! / (1!×1!×1!×1!×1!)	120 (distinct case)

MISSISSIPPI Example in Detail:

11 letters total
M appears 1 time
I appears 4 times
S appears 4 times
P appears 2 times

Distinct arrangements = 11! / (1! × 4! × 4! × 2!) = 39,916,800 / (1 × 24 × 24 × 2) = 34,650

Compare to 11! = 39,916,800 if all letters were distinct. The duplicates reduce the count by a factor of over 1,100.

Multiset Combinations:

Selecting k elements from a multiset (without regard to order) is more complex. If we can pick each element type multiple times up to its availability, we use techniques from generating functions or dynamic programming to count. For generation, we adapt our combination algorithm to respect element multiplicities.

The binomial coefficient generalization

The expression n! / (n₁! × n₂! × ... × nₖ!) is called the multinomial coefficient, written as (n; n₁, n₂, ..., nₖ). It generalizes the binomial coefficient to multiple groups and appears throughout combinatorics and probability.

Why Naive Algorithms Produce Duplicates

To understand the solutions, we must first understand why the problem arises. Both the inserting and swapping approaches fail when elements repeat, but for slightly different reasons.

Inserting Approach Failure:

With input [1, 1, 2], the algorithm tracks indices via the 'used' array, not values. Index 0 and index 1 both contain 1. Selecting index 0, then index 1, produces [1, 1, 2]. Selecting index 1, then index 0, produces [1, 1, 2]—the same arrangement! The algorithm sees two different paths but identical outputs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function naivePermuteWithDuplicates(elements: number[]): number[][] {
    const results: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Demonstrate the problem
const input = [1, 1, 2];
const naiveResults = naivePermuteWithDuplicates(input);
 
console.log(`Input: [${input}]`);
console.log(`Total permutations generated: ${naiveResults.length}`);
console.log("Generated permutations:");
naiveResults.forEach((p, i) => {
    console.log(`  #${i + 1}: [${p}]`);
});
 
// Count unique
const uniqueSet = new Set(naiveResults.map(p => p.join(",")));
console.log(`\nUnique permutations: ${uniqueSet.size}`);
console.log(`Duplicates generated: ${naiveResults.length - uniqueSet.size}`);
console.log(`\nExpected: 3! / (2! × 1!) = 6 / 2 = 3 unique`);

Output:

Input: [1, 1, 2]
Total permutations generated: 6
Generated permutations:
  #1: [1, 1, 2]
  #2: [1, 2, 1]
  #3: [1, 1, 2]  ← Duplicate!
  #4: [1, 2, 1]  ← Duplicate!
  #5: [2, 1, 1]
  #6: [2, 1, 1]  ← Duplicate!

Unique permutations: 3
Duplicates generated: 3

Expected: 3! / (2! × 1!) = 6 / 2 = 3 unique

Swapping Approach Failure:

Similarly, swapping [1, 1, 2] at position 0 with itself (no-op) differs from swapping with position 1 (also no effective change since both values are 1). The algorithm perceives two different swaps producing identical results.

The Consequence of Duplicates

Generating duplicates isn't just inefficient—it can cause incorrect behavior:

• Counting algorithms give wrong totals • Random selection becomes biased toward arrangements with more duplicates • Memory usage inflates unnecessarily • Applications expecting unique outputs may fail or produce incorrect results

Strategy 1: Post-Filtering with a Set

The simplest (but least efficient) solution is to generate all permutations naively, then filter out duplicates using a set or by sorting and removing adjacent duplicates.

Approach:

Generate all n! permutations using any standard algorithm
Store results in a Set (using a string/tuple key for comparison)
The Set automatically deduplicates
Convert the Set back to an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
function permuteWithPostFilter(elements: number[]): number[][] {
    const allPermutations: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            allPermutations.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    
    // Post-filter: use a Set to deduplicate
    const uniqueSet = new Set<string>();
    const uniquePermutations: number[][] = [];
    
    for (const perm of allPermutations) {
        const key = perm.join(",");
        if (!uniqueSet.has(key)) {
            uniqueSet.add(key);
            uniquePermutations.push(perm);
        }
    }
    
    return uniquePermutations;
}
 
// Cleaner version using Map
function permuteWithSetFilter(elements: number[]): number[][] {
    const seen = new Map<string, number[]>();
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            const key = current.join(",");
            if (!seen.has(key)) {
                seen.set(key, [...current]);
            }
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return Array.from(seen.values());
}
 
const result = permuteWithPostFilter([1, 1, 2]);
console.log("Post-filtered permutations of [1, 1, 2]:");
result.forEach(p => console.log(p.join(",")));

Advantages

•Simple to implement
•Uses existing permutation code unchanged
•Guaranteed correct (eventually removes all duplicates)
•Works with any input type that can be stringified

Disadvantages

•Still generates O(n!) permutations—very slow for large n
•O(n!) memory for the set to store intermediate results
•String conversion overhead for comparison
•Wasteful: generates data only to throw it away

Use Only as Last Resort

Post-filtering should only be used when: • The input is very small (n ≤ 6-7) • You need a quick fix and will optimize later • The input rarely has duplicates (filtering is cheap in the common case)

For any serious application, use one of the smarter approaches below.

Strategy 2: Runtime Visited Set (Progressive Filtering)

A better approach is to check for duplicates during generation, avoiding unnecessary recursion into branches that will produce duplicates.

Approach:

Maintain a 'visited' set at each recursion level that tracks which values (not indices) we've already tried for the current position. If we encounter a value we've already tried at this position, skip it.

Key Insight:

Duplicates arise when the same value appears at the same position via different selection paths. If we ensure each distinct value is tried only once per position, we eliminate duplicates at the source.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function permuteUniqueWithVisited(elements: number[]): number[][] {
    const results: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Track which VALUES we've tried at this position
        const visitedAtThisLevel = new Set<number>();
        
        for (let i = 0; i < n; i++) {
            // Skip if this index is already used in current permutation
            if (used[i]) continue;
            
            // Skip if we've already tried this VALUE at this position
            if (visitedAtThisLevel.has(elements[i])) continue;
            
            // Mark this value as tried for this level
            visitedAtThisLevel.add(elements[i]);
            
            // Standard backtracking
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Test on various inputs
console.log("Permutations of [1, 1, 2]:");
permuteUniqueWithVisited([1, 1, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nPermutations of [1, 1, 1]:");
permuteUniqueWithVisited([1, 1, 1]).forEach(p => console.log(p.join(",")));
 
console.log("\nPermutations of [1, 2, 2]:");
permuteUniqueWithVisited([1, 2, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nCount for AABB:");
console.log(`Generated: ${permuteUniqueWithVisited([1,1,2,2]).length}`);
console.log(`Expected: 4!/(2!×2!) = 24/4 = 6`);

How It Works:

Consider generating permutations of [1, 1, 2] at position 0:

i=0: value=1, not in visited → add to visited, recurse
i=1: value=1, already in visited → SKIP (avoids duplicate branch!)
i=2: value=2, not in visited → add to visited, recurse

By skipping i=1, we avoid the entire subtree that would duplicate i=0's results.

Complexity:

Time: O(unique permutations × n) — much better when duplicates exist
Space: O(n) for the visited set at each level × O(n) recursion depth = O(n²) for visited sets total, plus O(n) for used array and current

Visited Set is Per-Level

Critically, the visited set is declared inside the backtrack function, so it's fresh for each recursion level. A value that was visited at position 0 can still appear at position 1, 2, etc. We only skip duplicates at the same position.

Strategy 3: The Elegant 'Sorted Skip' Technique

The most elegant and commonly used approach combines sorting with a skip condition. By sorting the input first, duplicates become adjacent. We can then skip duplicates with a simple condition that doesn't require any additional data structures.

Approach:

Sort the input array (grouping duplicates together)
During generation, skip an element if:
- It equals the previous element, AND
- The previous element is not currently used

Key Insight:

For a group of identical elements, we establish an ordering: always use the first available one from the group. If we're considering the second copy but the first copy isn't used, skip—we should use the first copy instead. This ensures we always pick identical elements in their original sorted order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function permuteUniqueSortedSkip(elements: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            // Skip if already used
            if (used[i]) continue;
            
            // THE KEY CONDITION: Skip duplicate if previous duplicate is unused
            // If sorted[i] equals sorted[i-1] and sorted[i-1] is not used,
            // we should use sorted[i-1] first, so skip sorted[i]
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) {
                continue;
            }
            
            used[i] = true;
            current.push(sorted[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Demonstration with tracing
function permuteUniqueWithTrace(elements: number[]): void {
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(depth: number): void {
        const indent = "  ".repeat(depth);
        
        if (current.length === n) {
            console.log(`${indent}→ FOUND: [${current}]`);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) {
                console.log(`${indent}i=${i} value=${sorted[i]}: SKIP (prev unused duplicate)`);
                continue;
            }
            
            console.log(`${indent}i=${i} value=${sorted[i]}: SELECT`);
            used[i] = true;
            current.push(sorted[i]);
            backtrack(depth + 1);
            current.pop();
            used[i] = false;
        }
    }
    
    console.log(`Sorted input: [${sorted}]`);
    backtrack(0);
}
 
console.log("Trace for [1, 1, 2]:");
permuteUniqueWithTrace([1, 1, 2]);

Understanding the Skip Condition:

Let's analyze if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]):

i > 0: Only check for previous element if one exists
sorted[i] === sorted[i - 1]: Current element equals its predecessor (they're duplicates)
!used[i - 1]: The predecessor is NOT currently in the permutation

Why this works:

When we have duplicates like [1₁, 1₂, 2] (subscripts distinguish copies):

If we want to place a '1' at some position, we should prefer 1₁ over 1₂
If 1₁ is available (!used[i-1]), don't use 1₂ (current element)
If 1₁ is already used (used[i-1] is true), then using 1₂ is fine

This establishes a canonical ordering: among duplicates, always use the leftmost available.

Why This Condition is Superior

Compared to the runtime visited set:

• No extra data structure — just the sorted array and a simple check • O(1) check per element instead of set operations • Conceptually elegant — the invariant is clear: use leftmost among duplicates • Industry standard — this is the approach used in most professional codebases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function permuteUnique(nums: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...nums].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;
            
            used[i] = true;
            current.push(sorted[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Comprehensive tests
function test(input: number[]): void {
    const result = permuteUnique(input);
    console.log(`\nInput: [${input}]`);
    console.log(`Count: ${result.length}`);
    result.forEach(p => console.log(`  [${p}]`));
}
 
// Test cases
test([1, 2, 3]);   // No duplicates: expect 6
test([1, 1, 2]);   // One duplicate pair: expect 3
test([1, 1, 1]);   // All same: expect 1
test([1, 2, 2]);   // Duplicate at end: expect 3
test([1, 1, 2, 2]); // Two pairs: expect 6

Handling Duplicates with the Swapping Approach

The swapping approach can also handle duplicates, but the technique differs slightly because we're not selecting from a pool—we're swapping in place. The key insight remains: don't swap an element into a position if we've already placed the same value there.

Approach:

At each position, track which values have been swapped into that position. Skip swaps that would repeat a value we've already tried at that position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function permuteUniqueSwap(elements: number[]): number[][] {
    const results: number[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function backtrack(start: number): void {
        if (start === n) {
            results.push([...arr]);
            return;
        }
        
        // Track which values we've swapped into position 'start'
        const triedAtThisPosition = new Set<number>();
        
        for (let i = start; i < n; i++) {
            // Skip if we've already tried this value at this position
            if (triedAtThisPosition.has(arr[i])) continue;
            
            triedAtThisPosition.add(arr[i]);
            
            // Swap element at i to position start
            [arr[start], arr[i]] = [arr[i], arr[start]];
            backtrack(start + 1);
            [arr[start], arr[i]] = [arr[i], arr[start]]; // Restore
        }
    }
    
    backtrack(0);
    return results;
}
 
// Alternative: Sort first for consistent ordering
function permuteUniqueSwapSorted(elements: number[]): number[][] {
    const results: number[][] = [];
    const arr = [...elements].sort((a, b) => a - b);
    const n = arr.length;
    
    function backtrack(start: number): void {
        if (start === n) {
            results.push([...arr]);
            return;
        }
        
        for (let i = start; i < n; i++) {
            // Skip duplicate: same value at different position, 
            // but we've already placed this value at 'start'
            if (i > start && arr[i] === arr[start]) continue;
            
            // Additional check: skip if arr[i] equals any element between start and i
            // This handles cases where duplicates aren't adjacent after swaps
            let shouldSkip = false;
            for (let j = start; j < i; j++) {
                if (arr[j] === arr[i]) {
                    shouldSkip = true;
                    break;
                }
            }
            if (shouldSkip) continue;
            
            [arr[start], arr[i]] = [arr[i], arr[start]];
            backtrack(start + 1);
            [arr[start], arr[i]] = [arr[i], arr[start]];
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("Swap approach with duplicates [1, 1, 2]:");
permuteUniqueSwap([1, 1, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nSwap approach with duplicates [1, 2, 2]:");
permuteUniqueSwap([1, 2, 2]).forEach(p => console.log(p.join(",")));

Swapping Complexity with Duplicates

The swapping approach with duplicates is trickier than the inserting approach because swaps can rearrange elements, making the 'skip if previous unused' condition harder to apply directly. The set-based approach (tracking tried values per position) is more reliable for the swapping method.

Combinations with Duplicate Elements

The same techniques extend to generating unique combinations from a multiset. The sorted-skip approach works elegantly:

Sort the input (grouping duplicates)
Use the standard combination algorithm with startIndex
Add the skip condition: if the current element equals the previous AND we're not picking the first in the group at this level, skip

The Skip Condition for Combinations:

if (i > startIndex && elements[i] === elements[i - 1]) continue;

This says: within the choices for this position, don't pick a duplicate of something we just skipped. If elements[i-1] was considered but not chosen earlier in this loop iteration, don't choose elements[i] either (it would create a duplicate combination).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function combinationsUnique(elements: number[], k: number): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const current: number[] = [];
    
    function backtrack(start: number): void {
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Pruning
        if (n - start < k - current.length) return;
        
        for (let i = start; i < n; i++) {
            // Skip duplicate at this level
            // If i > start and current equals previous, previous was skipped
            // in an earlier iteration of this loop, so skip current too
            if (i > start && sorted[i] === sorted[i - 1]) continue;
            
            current.push(sorted[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
// Test cases
console.log("2-combinations from [1, 1, 2]:");
combinationsUnique([1, 1, 2], 2).forEach(c => console.log(c.join(",")));
// Expected: [1,1], [1,2] (not [1,2] twice)
 
console.log("\n2-combinations from [1, 1, 2, 2]:");
combinationsUnique([1, 1, 2, 2], 2).forEach(c => console.log(c.join(",")));
// Expected: [1,1], [1,2], [2,2]
 
console.log("\n3-combinations from [1, 1, 1, 2, 2]:");
combinationsUnique([1, 1, 1, 2, 2], 3).forEach(c => console.log(c.join(",")));
// Expected: [1,1,1], [1,1,2], [1,2,2]

Understanding the Combination Skip Condition:

For combinations, the condition is simpler than permutations:

if (i > start && sorted[i] === sorted[i - 1]) continue;

Why?

In combinations, we iterate i from start to n-1. If i > start, then index i-1 ≥ start, meaning sorted[i-1] was a valid candidate at this level but we chose not to include it (either it was chosen earlier in a previous iteration, or we're past it now). If sorted[i] === sorted[i-1] and we didn't include sorted[i-1], including sorted[i] would produce a duplicate combination.

Key Difference from Permutations:

In permutations, we check !used[i-1] because the previous element might be used elsewhere in the permutation. In combinations, once we pass an index, we never revisit it, so if i > start, the previous index was definitely not included at this level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function subsetsUnique(elements: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const current: number[] = [];
    
    function backtrack(start: number): void {
        // Record every subset (including partial ones)
        results.push([...current]);
        
        for (let i = start; i < n; i++) {
            // Skip duplicates at this level
            if (i > start && sorted[i] === sorted[i - 1]) continue;
            
            current.push(sorted[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("All unique subsets of [1, 2, 2]:");
subsetsUnique([1, 2, 2]).forEach(s => console.log(`[${s.join(",")}]`));
// Expected: [], [1], [1,2], [1,2,2], [2], [2,2]
// NOT: [], [1], [1,2], [1,2], [1,2,2], [2], [2], [2,2]

Complexity Analysis and Performance

Understanding the performance characteristics of each approach helps select the right algorithm for your constraints.

Post-Filtering Approach:

Time: O(n! × n) to generate all permutations, plus O(n! × n) to deduplicate
Space: O(n!) for storing all generated permutations
Regardless of duplicate count, we do O(n!) work

Runtime Visited Set:

Time: O(unique permutations × n)
Space: O(n²) for visited sets at each level
Better: we avoid recursing into duplicate branches

Sorted Skip:

Time: O(n log n) for sorting + O(unique permutations × n)
Space: O(n) for used array + O(n) for current
Best: minimal overhead, no extra data structures during generation

Performance Comparison: Generating Permutations of 'AAABBBC'
Approach	Generated	Unique	Wasted Computation
Naive (no dedup)	7! = 5,040	5,040	Outputs 5,040 but only 140 unique
Post-Filter	5,040 generated	140 kept	Generates 36× more than needed
Runtime Visited	~140 (directly)	140	Minimal waste
Sorted Skip	~140 (directly)	140	Minimal waste

Empirical Benchmark:

For increasingly duplicate-heavy inputs, the smart approaches significantly outperform naive generation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function benchmark<T>(name: string, fn: () => T): [string, number, T] {
    const start = performance.now();
    const result = fn();
    const elapsed = performance.now() - start;
    return [name, elapsed, result];
}
 
// Test inputs of varying duplication
const testCases = [
    { name: "[1,2,3,4,5]", input: [1, 2, 3, 4, 5] },
    { name: "[1,1,2,2,3]", input: [1, 1, 2, 2, 3] },
    { name: "[1,1,1,2,2]", input: [1, 1, 1, 2, 2] },
    { name: "[1,1,1,1,2]", input: [1, 1, 1, 1, 2] },
    { name: "[1,1,1,1,1]", input: [1, 1, 1, 1, 1] },
];
 
console.log("Benchmark: Unique Permutation Generation\n");
console.log("Input | Naive (n!) | Smart | Unique Count | Speedup");
console.log("-".repeat(55));
 
for (const { name, input } of testCases) {
    // Naive approach (for comparison)
    const [, naiveTime] = benchmark("Naive", () => {
        // Simulate n! work
        let count = 1;
        for (let i = 2; i <= input.length; i++) count *= i;
        return count;
    });
    
    // Smart approach
    const [, smartTime, result] = benchmark("Smart", () => permuteUnique(input));
    
    const uniqueCount = result.length;
    console.log(`${name.padEnd(12)} | ${naiveTime.toFixed(2).padStart(8)}ms | ${smartTime.toFixed(2).padStart(5)}ms | ${String(uniqueCount).padStart(6)} | N/A`);
}
 
// Larger test to show real difference
console.log("\n--- Larger Test (8 elements with duplicates) ---");
const largeInput = [1, 1, 1, 2, 2, 2, 3, 3];
console.log(`Input: [${largeInput}]`);
console.log(`Naive would generate: ${[...Array(8).keys()].reduce((a, i) => a * (i + 1), 1)} = 40,320`);
 
const [, largeTime, largeResult] = benchmark("Smart", () => permuteUnique(largeInput));
console.log(`Smart generated: ${largeResult.length} unique permutations`);
console.log(`Expected: 8!/(3!×3!×2!) = 40320/(6×6×2) = 560`);
console.log(`Time: ${largeTime.toFixed(2)}ms`);

Optimal Unique Permutation Count

The sorted-skip and visited-set approaches generate exactly n!/(n₁!×n₂!×...×nₖ!) permutations with O(1) overhead per permutation (beyond the O(n) copy). They're essentially optimal—you can't generate fewer outputs since each is unique, and you must read each output element.

Summary and Best Practices

We've explored the challenge of generating unique permutations and combinations when the input contains duplicate elements. Here are the essential takeaways:

The Problem:

Naive algorithms treat identical elements as distinct, generating duplicate outputs. For a multiset with n elements, naive approaches generate n! outputs but only n!/(n₁!×n₂!×...×nₖ!) are unique.

The Solutions:

Post-Filtering: Generate all, then deduplicate. Simple but wasteful—O(n!) work and memory regardless of duplicates.
Runtime Visited Set: Track tried values per position. Effective but requires O(n) extra space per recursion level.
Sorted Skip: Sort input, skip if current equals previous and previous is unused (permutations) or skipped (combinations). Elegant, efficient, minimal overhead.

Key Takeaways

•Sorted-skip is the industry standard — memorize this pattern for coding interviews
•Permutation condition: i > 0 && nums[i] == nums[i-1] && !used[i-1]
•Combination condition: i > start && nums[i] == nums[i-1]
•Always sort first — this is what enables the skip condition to work
•The principle is canonical ordering — among duplicates, always pick the leftmost available
•Smart approaches achieve optimal complexity — O(unique outputs × n) with minimal overhead

Quick Reference: Skip Conditions
Problem Type	Sort First?	Skip Condition
Unique Permutations	Yes	i > 0 && arr[i] == arr[i-1] && !used[i-1]
Unique Combinations	Yes	i > start && arr[i] == arr[i-1]
Unique Subsets	Yes	i > start && arr[i] == arr[i-1]
Swapping (Permutations)	Optional	Use runtime Set per position

This Completes the Module:

You've now mastered the full spectrum of permutation and combination generation:

Generating All Permutations: Multiple approaches for arranging n elements
Generating K-Combinations: Selecting k elements without order
Swapping vs Inserting: Understanding both paradigms and when to use each
Handling Duplicates: Elegant techniques to avoid duplicate outputs

These skills form the foundation for solving countless backtracking problems in algorithms, from puzzles like N-Queens to optimization problems in scheduling and resource allocation.

Module Complete

Congratulations! You've completed the Permutations & Combinations module. You now possess comprehensive knowledge of generating arrangements and selections, handling edge cases like duplicates, and choosing appropriate algorithms for different constraints. These techniques will serve you well in technical interviews, competitive programming, and real-world software engineering.

Handling Duplicates

The Duplicate Dilemma

All our previous algorithms assumed distinct elements. But what happens when the input contains duplicates? Consider generating permutations of [1, 1, 2]. A naive algorithm would produce:

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

What You Will Master

By the end of this page, you will understand:

Mathematical Foundations: Multiset Counting

Multiset Permutation Formula:

For a multiset with n elements total, where element types appear with frequencies n₁, n₂, ..., nₖ (where n₁ + n₂ + ... + nₖ = n), the number of distinct permutations is:

n! / (n₁! × n₂! × ... × nₖ!)

Intuition:

Multiset Permutation Examples
Multiset	Frequencies	Formula	Count
{A, A, B}	A:2, B:1	3! / (2! × 1!)	3
{1, 1, 2, 2}	1:2, 2:2	4! / (2! × 2!)	6
{a, a, a, b, b}	a:3, b:2	5! / (3! × 2!)	10
MISSISSIPPI	M:1, I:4, S:4, P:2	11! / (1! × 4! × 4! × 2!)	34,650
{1, 2, 3, 4, 5}	all:1	5! / (1!×1!×1!×1!×1!)	120 (distinct case)

MISSISSIPPI Example in Detail:

11 letters total
M appears 1 time
I appears 4 times
S appears 4 times
P appears 2 times

Distinct arrangements = 11! / (1! × 4! × 4! × 2!) = 39,916,800 / (1 × 24 × 24 × 2) = 34,650

Compare to 11! = 39,916,800 if all letters were distinct. The duplicates reduce the count by a factor of over 1,100.

Multiset Combinations:

The binomial coefficient generalization

Why Naive Algorithms Produce Duplicates

To understand the solutions, we must first understand why the problem arises. Both the inserting and swapping approaches fail when elements repeat, but for slightly different reasons.

Inserting Approach Failure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function naivePermuteWithDuplicates(elements: number[]): number[][] {
    const results: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Demonstrate the problem
const input = [1, 1, 2];
const naiveResults = naivePermuteWithDuplicates(input);
 
console.log(`Input: [${input}]`);
console.log(`Total permutations generated: ${naiveResults.length}`);
console.log("Generated permutations:");
naiveResults.forEach((p, i) => {
    console.log(`  #${i + 1}: [${p}]`);
});
 
// Count unique
const uniqueSet = new Set(naiveResults.map(p => p.join(",")));
console.log(`\nUnique permutations: ${uniqueSet.size}`);
console.log(`Duplicates generated: ${naiveResults.length - uniqueSet.size}`);
console.log(`\nExpected: 3! / (2! × 1!) = 6 / 2 = 3 unique`);

Output:

Input: [1, 1, 2]
Total permutations generated: 6
Generated permutations:
  #1: [1, 1, 2]
  #2: [1, 2, 1]
  #3: [1, 1, 2]  ← Duplicate!
  #4: [1, 2, 1]  ← Duplicate!
  #5: [2, 1, 1]
  #6: [2, 1, 1]  ← Duplicate!

Unique permutations: 3
Duplicates generated: 3

Expected: 3! / (2! × 1!) = 6 / 2 = 3 unique

Swapping Approach Failure:

The Consequence of Duplicates

Generating duplicates isn't just inefficient—it can cause incorrect behavior:

Strategy 1: Post-Filtering with a Set

The simplest (but least efficient) solution is to generate all permutations naively, then filter out duplicates using a set or by sorting and removing adjacent duplicates.

Approach:

Generate all n! permutations using any standard algorithm
Store results in a Set (using a string/tuple key for comparison)
The Set automatically deduplicates
Convert the Set back to an array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
function permuteWithPostFilter(elements: number[]): number[][] {
    const allPermutations: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            allPermutations.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    
    // Post-filter: use a Set to deduplicate
    const uniqueSet = new Set<string>();
    const uniquePermutations: number[][] = [];
    
    for (const perm of allPermutations) {
        const key = perm.join(",");
        if (!uniqueSet.has(key)) {
            uniqueSet.add(key);
            uniquePermutations.push(perm);
        }
    }
    
    return uniquePermutations;
}
 
// Cleaner version using Map
function permuteWithSetFilter(elements: number[]): number[][] {
    const seen = new Map<string, number[]>();
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            const key = current.join(",");
            if (!seen.has(key)) {
                seen.set(key, [...current]);
            }
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return Array.from(seen.values());
}
 
const result = permuteWithPostFilter([1, 1, 2]);
console.log("Post-filtered permutations of [1, 1, 2]:");
result.forEach(p => console.log(p.join(",")));

Advantages

•Simple to implement
•Uses existing permutation code unchanged
•Guaranteed correct (eventually removes all duplicates)
•Works with any input type that can be stringified

Disadvantages

•Still generates O(n!) permutations—very slow for large n
•O(n!) memory for the set to store intermediate results
•String conversion overhead for comparison
•Wasteful: generates data only to throw it away

Use Only as Last Resort

For any serious application, use one of the smarter approaches below.

Strategy 2: Runtime Visited Set (Progressive Filtering)

A better approach is to check for duplicates during generation, avoiding unnecessary recursion into branches that will produce duplicates.

Approach:

Key Insight:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function permuteUniqueWithVisited(elements: number[]): number[][] {
    const results: number[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        // Track which VALUES we've tried at this position
        const visitedAtThisLevel = new Set<number>();
        
        for (let i = 0; i < n; i++) {
            // Skip if this index is already used in current permutation
            if (used[i]) continue;
            
            // Skip if we've already tried this VALUE at this position
            if (visitedAtThisLevel.has(elements[i])) continue;
            
            // Mark this value as tried for this level
            visitedAtThisLevel.add(elements[i]);
            
            // Standard backtracking
            used[i] = true;
            current.push(elements[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Test on various inputs
console.log("Permutations of [1, 1, 2]:");
permuteUniqueWithVisited([1, 1, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nPermutations of [1, 1, 1]:");
permuteUniqueWithVisited([1, 1, 1]).forEach(p => console.log(p.join(",")));
 
console.log("\nPermutations of [1, 2, 2]:");
permuteUniqueWithVisited([1, 2, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nCount for AABB:");
console.log(`Generated: ${permuteUniqueWithVisited([1,1,2,2]).length}`);
console.log(`Expected: 4!/(2!×2!) = 24/4 = 6`);

How It Works:

Consider generating permutations of [1, 1, 2] at position 0:

i=0: value=1, not in visited → add to visited, recurse
i=1: value=1, already in visited → SKIP (avoids duplicate branch!)
i=2: value=2, not in visited → add to visited, recurse

By skipping i=1, we avoid the entire subtree that would duplicate i=0's results.

Complexity:

Time: O(unique permutations × n) — much better when duplicates exist
Space: O(n) for the visited set at each level × O(n) recursion depth = O(n²) for visited sets total, plus O(n) for used array and current

Visited Set is Per-Level

Strategy 3: The Elegant 'Sorted Skip' Technique

Approach:

Sort the input array (grouping duplicates together)
During generation, skip an element if:
- It equals the previous element, AND
- The previous element is not currently used

Key Insight:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function permuteUniqueSortedSkip(elements: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            // Skip if already used
            if (used[i]) continue;
            
            // THE KEY CONDITION: Skip duplicate if previous duplicate is unused
            // If sorted[i] equals sorted[i-1] and sorted[i-1] is not used,
            // we should use sorted[i-1] first, so skip sorted[i]
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) {
                continue;
            }
            
            used[i] = true;
            current.push(sorted[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Demonstration with tracing
function permuteUniqueWithTrace(elements: number[]): void {
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(depth: number): void {
        const indent = "  ".repeat(depth);
        
        if (current.length === n) {
            console.log(`${indent}→ FOUND: [${current}]`);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) {
                console.log(`${indent}i=${i} value=${sorted[i]}: SKIP (prev unused duplicate)`);
                continue;
            }
            
            console.log(`${indent}i=${i} value=${sorted[i]}: SELECT`);
            used[i] = true;
            current.push(sorted[i]);
            backtrack(depth + 1);
            current.pop();
            used[i] = false;
        }
    }
    
    console.log(`Sorted input: [${sorted}]`);
    backtrack(0);
}
 
console.log("Trace for [1, 1, 2]:");
permuteUniqueWithTrace([1, 1, 2]);

Understanding the Skip Condition:

Let's analyze if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]):

i > 0: Only check for previous element if one exists
sorted[i] === sorted[i - 1]: Current element equals its predecessor (they're duplicates)
!used[i - 1]: The predecessor is NOT currently in the permutation

Why this works:

When we have duplicates like [1₁, 1₂, 2] (subscripts distinguish copies):

If we want to place a '1' at some position, we should prefer 1₁ over 1₂
If 1₁ is available (!used[i-1]), don't use 1₂ (current element)
If 1₁ is already used (used[i-1] is true), then using 1₂ is fine

This establishes a canonical ordering: among duplicates, always use the leftmost available.

Why This Condition is Superior

Compared to the runtime visited set:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function permuteUnique(nums: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...nums].sort((a, b) => a - b);
    const n = sorted.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: number[] = [];
    
    function backtrack(): void {
        if (current.length === n) {
            results.push([...current]);
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && sorted[i] === sorted[i - 1] && !used[i - 1]) continue;
            
            used[i] = true;
            current.push(sorted[i]);
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
    
    backtrack();
    return results;
}
 
// Comprehensive tests
function test(input: number[]): void {
    const result = permuteUnique(input);
    console.log(`\nInput: [${input}]`);
    console.log(`Count: ${result.length}`);
    result.forEach(p => console.log(`  [${p}]`));
}
 
// Test cases
test([1, 2, 3]);   // No duplicates: expect 6
test([1, 1, 2]);   // One duplicate pair: expect 3
test([1, 1, 1]);   // All same: expect 1
test([1, 2, 2]);   // Duplicate at end: expect 3
test([1, 1, 2, 2]); // Two pairs: expect 6

Handling Duplicates with the Swapping Approach

Approach:

At each position, track which values have been swapped into that position. Skip swaps that would repeat a value we've already tried at that position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
function permuteUniqueSwap(elements: number[]): number[][] {
    const results: number[][] = [];
    const arr = [...elements];
    const n = arr.length;
    
    function backtrack(start: number): void {
        if (start === n) {
            results.push([...arr]);
            return;
        }
        
        // Track which values we've swapped into position 'start'
        const triedAtThisPosition = new Set<number>();
        
        for (let i = start; i < n; i++) {
            // Skip if we've already tried this value at this position
            if (triedAtThisPosition.has(arr[i])) continue;
            
            triedAtThisPosition.add(arr[i]);
            
            // Swap element at i to position start
            [arr[start], arr[i]] = [arr[i], arr[start]];
            backtrack(start + 1);
            [arr[start], arr[i]] = [arr[i], arr[start]]; // Restore
        }
    }
    
    backtrack(0);
    return results;
}
 
// Alternative: Sort first for consistent ordering
function permuteUniqueSwapSorted(elements: number[]): number[][] {
    const results: number[][] = [];
    const arr = [...elements].sort((a, b) => a - b);
    const n = arr.length;
    
    function backtrack(start: number): void {
        if (start === n) {
            results.push([...arr]);
            return;
        }
        
        for (let i = start; i < n; i++) {
            // Skip duplicate: same value at different position, 
            // but we've already placed this value at 'start'
            if (i > start && arr[i] === arr[start]) continue;
            
            // Additional check: skip if arr[i] equals any element between start and i
            // This handles cases where duplicates aren't adjacent after swaps
            let shouldSkip = false;
            for (let j = start; j < i; j++) {
                if (arr[j] === arr[i]) {
                    shouldSkip = true;
                    break;
                }
            }
            if (shouldSkip) continue;
            
            [arr[start], arr[i]] = [arr[i], arr[start]];
            backtrack(start + 1);
            [arr[start], arr[i]] = [arr[i], arr[start]];
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("Swap approach with duplicates [1, 1, 2]:");
permuteUniqueSwap([1, 1, 2]).forEach(p => console.log(p.join(",")));
 
console.log("\nSwap approach with duplicates [1, 2, 2]:");
permuteUniqueSwap([1, 2, 2]).forEach(p => console.log(p.join(",")));

Swapping Complexity with Duplicates

Combinations with Duplicate Elements

The same techniques extend to generating unique combinations from a multiset. The sorted-skip approach works elegantly:

Sort the input (grouping duplicates)
Use the standard combination algorithm with startIndex
Add the skip condition: if the current element equals the previous AND we're not picking the first in the group at this level, skip

The Skip Condition for Combinations:

if (i > startIndex && elements[i] === elements[i - 1]) continue;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function combinationsUnique(elements: number[], k: number): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const current: number[] = [];
    
    function backtrack(start: number): void {
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Pruning
        if (n - start < k - current.length) return;
        
        for (let i = start; i < n; i++) {
            // Skip duplicate at this level
            // If i > start and current equals previous, previous was skipped
            // in an earlier iteration of this loop, so skip current too
            if (i > start && sorted[i] === sorted[i - 1]) continue;
            
            current.push(sorted[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
// Test cases
console.log("2-combinations from [1, 1, 2]:");
combinationsUnique([1, 1, 2], 2).forEach(c => console.log(c.join(",")));
// Expected: [1,1], [1,2] (not [1,2] twice)
 
console.log("\n2-combinations from [1, 1, 2, 2]:");
combinationsUnique([1, 1, 2, 2], 2).forEach(c => console.log(c.join(",")));
// Expected: [1,1], [1,2], [2,2]
 
console.log("\n3-combinations from [1, 1, 1, 2, 2]:");
combinationsUnique([1, 1, 1, 2, 2], 3).forEach(c => console.log(c.join(",")));
// Expected: [1,1,1], [1,1,2], [1,2,2]

Understanding the Combination Skip Condition:

For combinations, the condition is simpler than permutations:

if (i > start && sorted[i] === sorted[i - 1]) continue;

Why?

Key Difference from Permutations:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function subsetsUnique(elements: number[]): number[][] {
    const results: number[][] = [];
    const sorted = [...elements].sort((a, b) => a - b);
    const n = sorted.length;
    const current: number[] = [];
    
    function backtrack(start: number): void {
        // Record every subset (including partial ones)
        results.push([...current]);
        
        for (let i = start; i < n; i++) {
            // Skip duplicates at this level
            if (i > start && sorted[i] === sorted[i - 1]) continue;
            
            current.push(sorted[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
console.log("All unique subsets of [1, 2, 2]:");
subsetsUnique([1, 2, 2]).forEach(s => console.log(`[${s.join(",")}]`));
// Expected: [], [1], [1,2], [1,2,2], [2], [2,2]
// NOT: [], [1], [1,2], [1,2], [1,2,2], [2], [2], [2,2]

Complexity Analysis and Performance

Understanding the performance characteristics of each approach helps select the right algorithm for your constraints.

Post-Filtering Approach:

Time: O(n! × n) to generate all permutations, plus O(n! × n) to deduplicate
Space: O(n!) for storing all generated permutations
Regardless of duplicate count, we do O(n!) work

Runtime Visited Set:

Time: O(unique permutations × n)
Space: O(n²) for visited sets at each level
Better: we avoid recursing into duplicate branches

Sorted Skip:

Time: O(n log n) for sorting + O(unique permutations × n)
Space: O(n) for used array + O(n) for current
Best: minimal overhead, no extra data structures during generation

Performance Comparison: Generating Permutations of 'AAABBBC'
Approach	Generated	Unique	Wasted Computation
Naive (no dedup)	7! = 5,040	5,040	Outputs 5,040 but only 140 unique
Post-Filter	5,040 generated	140 kept	Generates 36× more than needed
Runtime Visited	~140 (directly)	140	Minimal waste
Sorted Skip	~140 (directly)	140	Minimal waste

Empirical Benchmark:

For increasingly duplicate-heavy inputs, the smart approaches significantly outperform naive generation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function benchmark<T>(name: string, fn: () => T): [string, number, T] {
    const start = performance.now();
    const result = fn();
    const elapsed = performance.now() - start;
    return [name, elapsed, result];
}
 
// Test inputs of varying duplication
const testCases = [
    { name: "[1,2,3,4,5]", input: [1, 2, 3, 4, 5] },
    { name: "[1,1,2,2,3]", input: [1, 1, 2, 2, 3] },
    { name: "[1,1,1,2,2]", input: [1, 1, 1, 2, 2] },
    { name: "[1,1,1,1,2]", input: [1, 1, 1, 1, 2] },
    { name: "[1,1,1,1,1]", input: [1, 1, 1, 1, 1] },
];
 
console.log("Benchmark: Unique Permutation Generation\n");
console.log("Input | Naive (n!) | Smart | Unique Count | Speedup");
console.log("-".repeat(55));
 
for (const { name, input } of testCases) {
    // Naive approach (for comparison)
    const [, naiveTime] = benchmark("Naive", () => {
        // Simulate n! work
        let count = 1;
        for (let i = 2; i <= input.length; i++) count *= i;
        return count;
    });
    
    // Smart approach
    const [, smartTime, result] = benchmark("Smart", () => permuteUnique(input));
    
    const uniqueCount = result.length;
    console.log(`${name.padEnd(12)} | ${naiveTime.toFixed(2).padStart(8)}ms | ${smartTime.toFixed(2).padStart(5)}ms | ${String(uniqueCount).padStart(6)} | N/A`);
}
 
// Larger test to show real difference
console.log("\n--- Larger Test (8 elements with duplicates) ---");
const largeInput = [1, 1, 1, 2, 2, 2, 3, 3];
console.log(`Input: [${largeInput}]`);
console.log(`Naive would generate: ${[...Array(8).keys()].reduce((a, i) => a * (i + 1), 1)} = 40,320`);
 
const [, largeTime, largeResult] = benchmark("Smart", () => permuteUnique(largeInput));
console.log(`Smart generated: ${largeResult.length} unique permutations`);
console.log(`Expected: 8!/(3!×3!×2!) = 40320/(6×6×2) = 560`);
console.log(`Time: ${largeTime.toFixed(2)}ms`);

Optimal Unique Permutation Count

Summary and Best Practices

We've explored the challenge of generating unique permutations and combinations when the input contains duplicate elements. Here are the essential takeaways:

The Problem:

The Solutions:

Post-Filtering: Generate all, then deduplicate. Simple but wasteful—O(n!) work and memory regardless of duplicates.
Runtime Visited Set: Track tried values per position. Effective but requires O(n) extra space per recursion level.
Sorted Skip: Sort input, skip if current equals previous and previous is unused (permutations) or skipped (combinations). Elegant, efficient, minimal overhead.

Key Takeaways

•Sorted-skip is the industry standard — memorize this pattern for coding interviews
•Permutation condition: i > 0 && nums[i] == nums[i-1] && !used[i-1]
•Combination condition: i > start && nums[i] == nums[i-1]
•Always sort first — this is what enables the skip condition to work
•The principle is canonical ordering — among duplicates, always pick the leftmost available
•Smart approaches achieve optimal complexity — O(unique outputs × n) with minimal overhead

Quick Reference: Skip Conditions
Problem Type	Sort First?	Skip Condition
Unique Permutations	Yes	i > 0 && arr[i] == arr[i-1] && !used[i-1]
Unique Combinations	Yes	i > start && arr[i] == arr[i-1]
Unique Subsets	Yes	i > start && arr[i] == arr[i-1]
Swapping (Permutations)	Optional	Use runtime Set per position

This Completes the Module:

You've now mastered the full spectrum of permutation and combination generation:

Generating All Permutations: Multiple approaches for arranging n elements
Generating K-Combinations: Selecting k elements without order
Swapping vs Inserting: Understanding both paradigms and when to use each
Handling Duplicates: Elegant techniques to avoid duplicate outputs

These skills form the foundation for solving countless backtracking problems in algorithms, from puzzles like N-Queens to optimization problems in scheduling and resource allocation.

Module Complete