Every Unique Ordering When Values May Repeat

Medium20–25 min

Topics

BacktrackingRecursionArray

Companies

AmazonGoogleBloomberg

Given an array of integers that may contain repeats, produce every distinct ordering of its elements — not every ordering of its positions, since two positions holding the same value shouldn't be treated as producing two different answers. Generating every raw arrangement and filtering afterward works: sort each row into a canonical form and collapse consecutive duplicates once everything is grouped together. But it always pays for the full n! generation first. Sorting the input up front and checking, at the moment a value is about to be tried, whether its identical predecessor is still idle or already part of the path being built, prevents a duplicate ordering from ever being generated in the first place — no cleanup pass required.

Test Case 1:

Input:nums = [3, 3, 5]

Output:[[3, 3, 5], [3, 5, 3], [5, 3, 3]]

Explanation:3 positions would normally give 3! = 6 orderings, but the two 3s are indistinguishable from each other, so only 3 orderings are actually different.

Test Case 2:

Input:nums = [7, 7]

Output:[[7, 7]]

Explanation:Both positions hold the same value, so despite 2! = 2 raw arrangements, there's only one distinct ordering.

Test Case 3:

Input:nums = [2]

Output:[[2]]

Explanation:A single element has exactly one ordering: itself.

Constraints

◆1 ≤ nums.length ≤ 7
◆-10 ≤ nums[i] ≤ 10, and values may repeat
◆Results are returned sorted in ascending (lexicographic) order for a stable, checkable answer

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Generate Every Raw Arrangement, Then Deduplicate

Brute

Treat every position as distinct regardless of its value and generate all n! raw arrangements exactly like the no-duplicates version. Repeated values then produce identical rows — sort every row into a canonical order, and walk through looking for consecutive equal rows to collapse away. Correct, but the full n! arrangements are always built first; if half of nums is one repeated value, most of that work is thrown away as duplicates immediately afterward.

TimeO(n! · n)

SpaceO(n! · n)

Java

Try it out

class Solution {
    public int[][] uniquePermutationsOf(int[] nums) {
        List<int[]> all = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        List<Integer> path = new ArrayList<>();
        generateAll(nums, used, path, all);
        all.sort((a, b) -> {
            for (int i = 0; i < a.length; i++) {
                if (a[i] != b[i]) return a[i] - b[i];
            }
            return 0;
        });
        List<int[]> result = new ArrayList<>();
        for (int[] row : all) {
            if (result.isEmpty() || !Arrays.equals(result.get(result.size() - 1), row)) {
                result.add(row);
            }
        }
        return result.toArray(new int[0][]);
    }

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

Optimal — Sorted, Skip a Same-Level Sibling Still Unused

Optimal

Sort first so equal values sit next to each other, then build paths with a used-flags array as usual — but add one more check before trying an index: if it holds the same value as the index right before it, AND that earlier one currently isn't in use, skip it. "Not in use" is the key detail — it means that identical earlier value has already been backtracked past at this exact position, so trying this one now would only rebuild a path already produced. When the earlier identical value IS still in use (it's part of the path currently being extended, not a sibling choice), there's nothing to skip — that's a distinct, legitimate continuation. This generates every unique ordering exactly once, in lexicographic order, with no separate deduplication pass needed at all.

TimeO(n!)

SpaceO(n)