LeetCode 47 – Permutations II

Permutations with duplicates in the input. One extra line — and it is a different extra line from the one Combination Sum II uses, which is the part that catches people who think they have already learned this trick.

The problem

Given a collection that may contain duplicates, return all unique permutations.

[1,1,2] -> [[1,1,2], [1,2,1], [2,1,1]]      three, not six
[1,2,3] -> all six, as usual
[2,2,2] -> [[2,2,2]]                        exactly one

[1,1,2] has 3! = 6 arrangements of its positions, but only 3 distinct sequences — swapping the two 1s produces something indistinguishable. Those are the duplicates to suppress.

Sorting is mandatory

As in Combination Sum II, the skip rule compares each element to its immediate predecessor, which only identifies duplicates when equal values are adjacent. Sort first or the rule silently misses cases. Here it is a correctness requirement, not an optimisation.

The line, and why it is not i > start

Permutations has no start index — every level scans from 0 — so the Combination Sum II rule has nothing to attach to. The question becomes: given two equal values, how do you tell "I am picking the second one instead of the first at this level" (duplicate) from "I am picking the second one as well as the first, deeper down" (legitimate)?

The answer is in used[]. Impose one rule: among equal values, always consume them left to right. Value i may only be taken if its equal predecessor i - 1 has already been taken:

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

Read !used[i - 1] as: the identical value before me is not in the current path, so it was either never tried at this level or has already been tried and undone. Either way, taking me now duplicates a branch that exists or existed.

When used[i - 1] is true, the predecessor is an ancestor in the current path — you are genuinely one level deeper, assembling [1,1,…], and that is allowed.

sorted [1a, 1b, 2]        (subscripts for illustration only)

level 0:  take 1a  -> ok
          take 1b  -> SKIP: nums equal, used[1a] is false
          take 2   -> ok

after taking 1a, level 1:
          take 1b  -> ALLOWED: used[1a] is true, so this is depth, not repetition
                      builds [1,1,2]

Java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);      // required: the skip compares neighbours
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> path,
                           int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            // Among equal values, only ever consume them left to right.
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.add(nums[i]);

            backtrack(result, path, nums, used);

            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Python

class Solution:
    def permuteUnique(self, nums: list[int]) -> list[list[int]]:
        nums.sort()                          # required, not an optimisation
        result = []
        path = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                result.append(path[:])
                return

            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue                 # equal predecessor not taken: duplicate branch

                used[i] = True
                path.append(nums[i])

                backtrack()

                path.pop()
                used[i] = False

        backtrack()
        return result

The used[i - 1] variant

Flipping the condition to used[i - 1] — allowing a duplicate only when its predecessor is not in the path — also produces the correct answer. It enforces right-to-left consumption instead, which is an equally valid canonical order.

It prunes later, though. The !used[i - 1] form rejects a duplicate branch at the moment it is proposed; the other form lets the first sibling run to completion before the pruning takes effect. Both are correct, one is faster, and knowing that they differ only in efficiency is a better answer than asserting one is "the" rule.

Three de-duplication rules, side by side

All three sort first and all three compare with the predecessor. What differs is how each one answers "am I at the same level, or deeper?" — and that question only has meaning because of the structure each algorithm has available.

Complexity

O(n · n!) worst case, when every value is distinct and no branch is ever pruned. With duplicates the real count is n! / (k₁! · k₂! · …), dividing by the factorial of each repeated value's multiplicity — [1,1,2] gives 3!/2! = 3. The pruning means those branches are never explored, not explored and discarded.

Space is O(n) for the path, the used array and the recursion depth.

What the interviewer is checking

• That you sort, and know it is required rather than tidy.
• !used[i - 1] — and that you can explain why i > start has nothing to attach to here.
• That you prune rather than collecting everything into a Set at the end.
• [1,1,2] returning exactly three, and [2,2,2] exactly one.
• Both pieces of state undone after recursing.
• Whether you can compare this rule against the one in Combination Sum II without confusing them.