Permutations II (LeetCode 47)

The problem

You get a list of integers that may contain duplicates. Return every distinct ordering of it. Two orderings that look the same (because they only swap two equal values) count once.

Input:  nums = [1, 1, 2]
Output: [[1,1,2], [1,2,1], [2,1,1]]

Plain Permutations would return 3! = 6 lists, but swapping the two 1s doesn’t create a new ordering, so only 6 / 2! = 3 are distinct.

How to think about it

Start with brute force. Generate all n! permutations and push each into a set of tuples. Correct, but if the input is [1,1,1,1,1,1,2] you build 5,040 permutations to keep 7. The interviewer will want the duplicates never to be built.

Where do duplicates come from? Call the two 1s 1a and 1b. The orderings 1a 1b 2 and 1b 1a 2 print identically. Every duplicate is just the same pattern with equal values used in a different order.

The key insight: force equal values to be used left to right. Sort the input so equal values sit together. Then add one rule: you may use nums[i] only if, when it equals nums[i-1], that earlier twin is already used in the current path. So 1b can only be placed after 1a. Of the 2! ways to order the two 1s, exactly one is allowed, and every distinct permutation is generated exactly once.

Read the condition carefully. Skip when i > 0 and nums[i] == nums[i-1] and not used[i-1]. “Twin not used” means 1a is free at this level, so picking 1b here would just repeat the branch that picks 1a. Mixing this up with the Subsets II rule (i > start) is the most common bug, because permutations have no start index.

Which pattern is this? Backtracking with de-duplication. The tell is “all orderings, input has duplicates, output must be unique”.

Approach

1. Sort nums.
2. bt(path, used): if path is full, record a copy.
3. For each i: skip if used[i], or if nums[i] == nums[i-1] and used[i-1] is false.
4. Otherwise mark used, append, recurse, then pop and unmark.
5. Start with bt([], [False] * n).

Solution

def permute_unique(nums):
    nums.sort(); res = []                     # equal values become neighbours
    def bt(path, used):
        if len(path) == len(nums): res.append(path[:]); return
        for i in range(len(nums)):
            # skip if taken, or if an equal twin to the left hasn't been used yet
            if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue
            used[i] = True; path.append(nums[i]); bt(path, used); path.pop(); used[i] = False
    bt([], [False] * len(nums)); return res
# permute_unique([1,1,2]) -> [[1,1,2],[1,2,1],[2,1,1]]

Dry run

On nums = [1, 1, 2] (indices 0, 1, 2):

Two branches are cut, and three unique permutations come out.

Complexity

• Time: O(n·n!) in the worst case (all distinct). With duplicates the tree is smaller: roughly n! divided by the factorials of each value’s count, times O(n) per copy.
• Space: O(n) extra for recursion, path and used.

Edge cases and pitfalls

• Forgetting to sort. The twin check only compares neighbours, so unsorted input leaks duplicates.
• Using used[i-1] instead of not used[i-1]. Surprisingly, that also produces the right answer (it forces right-to-left order instead), but it prunes much later and explores far more of the tree. Know which one you wrote and why.
• All equal values, e.g. [2,2,2], gives one permutation.
• Using a set of tuples to de-dup is an acceptable fallback if you get stuck, but say that you know the pruning version.

Related problems

• Permutations (LeetCode 46): the base template with distinct values.
• Subsets II (LeetCode 90): the same sort-then-skip idea for subsets, where the rule uses i > start.
• Combination Sum II (LeetCode 40): the subsets-style skip again, with a target sum.