Permutations II

MEDIUM✓ CHIP-TIMEDLC #47 — FULL STATEMENT ↗

The drill: Same as ordering a list every possible way, except values can repeat — return every distinct ordering exactly once, even though swapping two equal values produces a sequence that looks identical.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A list of numbers that may repeat arrives, and the task mirrors plain permutations: produce every ordering that uses each element exactly once.

Because values can repeat, swapping two equal numbers into each other's positions produces an ordering that looks exactly the same as the one it replaced — that duplicate must not appear twice in the output.

Two orderings are considered the same result only when the sequence of values matches position for position, ignoring which physical element supplied which value.

EX 01

nums = [1, 1]

→ [[1, 1]]

IDENTICAL PAIR COLLAPSES TO ONE ORDERING

EX 02

nums = [1, 2]

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

NO DUPLICATES, CONTROL CASE

EX 03

nums = [1, 1, 2]

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

values may repeat; the array itself stays short since output size is factorial
every element is used exactly once per ordering
duplicate-looking orderings collapse into a single entry in the output
output order between distinct orderings is free

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Treating every position as a distinct slot still works for counting arrangements, but two orderings that differ only by swapping equal values are the same output — that collision has to be prevented, not cleaned up after.

HINT 2 THE STRUCTURE

Sort the values first. At a given position, using a repeated value as anything but the FIRST fill for that position — among the values still available — just reproduces an ordering already built.

HINT 3 ONE STEP FROM THE ANSWER

Track which indices are used. At each position, skip index i when nums[i] equals nums[i − 1] and index i − 1 is currently unused — that's exactly the signal that this branch would only repeat work.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FREE-TWIN SKIPPATTERN · SORTED BACKTRACK, SKIP FREE TWINSnums = [1, 1, 2]

STEP 1

Three numbers, one duplicate pair: 1, 1, 2. Sorting groups the duplicates so a used-tracking rule can skip repeat orderings.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/permutations-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        used = [False] * n
        path = []
        res = []

        def backtrack():
            if len(path) == n:
                res.append(list(path))
                return
            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue  # predecessor twin still free — this branch repeats work
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return res

TIME O(N·N!)SPACE O(N)PYTHON · RACE PACE · 25 LN

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        used = [False] * n
        path = []
        found = set()

        def backtrack():
            if len(path) == n:
                found.add(tuple(path))
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                backtrack()
                path.pop()
                used[i] = False

        backtrack()
        return [list(t) for t in found]

TIME O(N·N!)SPACE O(N·N!)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        boolean[] used = new boolean[n];
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, used, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

TIME O(N·N!)SPACE O(N)JAVA · RACE PACE · 30 LN

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        boolean[] used = new boolean[n];
        Set<List<Integer>> found = new HashSet<>();
        backtrack(nums, used, new ArrayList<>(), found);
        return new ArrayList<>(found);
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> path, Set<List<Integer>> found) {
        if (path.size() == nums.length) {
            found.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtrack(nums, used, path, found);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

TIME O(N·N!)SPACE O(N·N!)JAVA · TRAINING PACE · 26 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED