Permutations II (with duplicates): sort then skip same-level duplicates

• Permutations II – generate all unique orderings of an array that may contain duplicates.
• Sort first – places equal values adjacent for neighbor comparison.
• used[] array – tracks which elements are currently placed in the permutation path.
• Skip guard – skip nums[i] if nums[i] == nums[i-1] and !used[i-1], enforcing canonical left-to-right placement of identical values.
• Time – O(n * n!) worst case for all-distinct elements.

What is the Permutations II problem?

Given an array that may contain duplicates, return all unique permutations. For example, [1, 1, 2] has three unique permutations: [1,1,2], [1,2,1], and [2,1,1], not the six you would get from treating both 1s as distinct.

package com.bank.dsa;

import java.util.List;

public interface UniquePermutationGenerator {
    List<List<Integer>> permuteUnique(int[] nums);
}

How does the sorting plus used-array approach work?

Sort the array so equal values are adjacent. Use a used[] boolean array to track which indices are currently part of the permutation path. At each recursion level, iterate all indices. Skip if the index is already used. Also skip if the current element equals the previous element and the previous is not used.

package com.bank.dsa;

import java.util.*;

public class BatchScheduler {
    public static List<List<Integer>> permuteUnique(int[] batchTypes) {
        Arrays.sort(batchTypes);
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[batchTypes.length];
        backtrack(batchTypes, used, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, boolean[] used,
                                   List<Integer> path, List<List<Integer>> result) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // Skip: same value as previous, and previous is not used
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] batches = {1, 1, 2};
        List<List<Integer>> schedules = permuteUnique(batches);
        for (List<Integer> s : schedules) {
            System.out.println(s);
        }
    }
}

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

Why does !used[i-1] prevent duplicates?

The condition !used[i-1] enforces that among equal values, an earlier copy must be placed before a later copy. If the previous equal element is not currently used in this branch, placing the current one would violate the canonical left-to-right order, creating a mirror-image duplicate. Skipping in this case prevents that.

// nums = [1a, 1b, 2]  (a and b are identical)
//
// Without skip: both [1a, 1b, 2] and [1b, 1a, 2] are generated
// With !used[i-1] skip: only [1a, 1b, 2] is generated
// because 1b is only placed after 1a is already used

What happens if you flip the condition to used[i-1]?

If you wrote used[i-1] instead of !used[i-1], you would keep duplicates and drop valid permutations. The direction of the condition matters because it determines whether the canonical order is "earlier before later" or "later before earlier".

// Wrong: used[i-1] keeps mirror duplicates
if (i > 0 && nums[i] == nums[i-1] && used[i-1]) continue;
// This skips when the previous IS used, which is the valid case

// Correct: !used[i-1] skips when previous is NOT used
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

How does the recursion tree look?

For [1, 1, 2], the recursion tree with the skip guard prunes branches where the second 1 is placed before the first 1.

Level 0: try 1a (used[0]=T), try 1b SKIP (!used[0]=F, skip), try 2
Level 1 under 1a: try 1b (used[1]=T), try 2
Level 1 under 2: try 1a, try 1b SKIP

Result: [1a,1b,2], [1a,2,1b], [2,1a,1b]
= [1,1,2], [1,2,1], [2,1,1]

What is the time complexity?

For all-distinct elements the cost is O(n * n!) because there are n! permutations, each taking O(n) to copy. With duplicates, branches are pruned, reducing the count. For example, [1, 1, 1] has only 1 unique permutation instead of 6.

All distinct:     O(n * n!)
All same:         O(n)  (one permutation)
Some duplicates:  between O(n) and O(n * n!)

What are common mistakes?

The most common mistake is flipping the !used[i-1] condition to used[i-1]. Another is forgetting to sort the array first, which makes the duplicate comparison ineffective. A third is not copying the path when adding to the result, which causes all entries to point to the same (eventually empty) list.

// Wrong: adding the same list reference
result.add(path); // all entries share the same list

// Correct: add a copy
result.add(new ArrayList<>(path));

Where else does this pattern appear?

The canonical-order technique for de-duplicating permutations applies whenever you enumerate orderings of elements with duplicates. It is the permutation analogue of the skip-same-level-duplicate pattern in Subsets II and Combination Sum II.

What should a senior engineer know?

A senior engineer explains the canonical-order invariant: among equal values, earlier copies are always placed before later copies. They know both the !used[i-1] and used[i-1] formulations, understand which one is correct and why, and can code it from memory. They also know that a HashMap-based frequency count approach avoids sorting but is more complex to implement.