Permutations II — Medium Problem & Solution

Problem statement

nums may contain repeated values. Return every distinct ordering (permutation) of its elements — two orderings that read the same value by value count once, even if they place different copies of a repeated value.

List the permutations in lexicographic order (compare value by value from the left).

Example 1

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

Example 2

Input: nums = [3,0,3,3]
Output: [[0,3,3,3],[3,0,3,3],[3,3,0,3],[3,3,3,0]]
Explanation: The three 3s are interchangeable, so only the position of the 0 matters.

Example 3

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

Constraints

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

How to solve Permutations II

Treat equal values as if they must be placed in index order. Every distinct permutation then has exactly one way to be built, and trying values in increasing order emits them lexicographically.

Approach

1. Sort nums and keep a used flag per index.
2. dfs fills the next position: for each unused index i, skip it if i > 0, nums[i] == nums[i - 1] and used[i - 1] is false.
3. Otherwise mark i, append nums[i], recurse, then undo both.
4. When the path has length n, record a copy.

Why it works

The skip rule means the copies of one value are always consumed left to right, so two builds that differ only by swapping equal copies cannot both happen — each distinct sequence appears once. Positions are filled left to right and, at each position, candidate values are tried in increasing order, which is exactly lexicographic order of the finished sequences.

Complexity

• Time — O(n · n!) in the worst case (all values distinct)
• Space — O(n) besides the output

Pitfalls

• Testing used[i - 1] instead of !used[i - 1] also removes duplicates but emits the permutations in a different order — and is much slower.
• Without sorting, equal values are not adjacent and duplicates slip through.
• Copy the path when recording it.

Reference solution

Python

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    a = sorted(nums)
    n = len(a)
    used = [False] * n
    out = []
    path = []

    def dfs():
        if len(path) == n:
            out.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            if i > 0 and a[i] == a[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(a[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return out

JavaScript

var permuteUnique = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var n = a.length;
    var used = new Array(n).fill(false);
    var out = [];
    var path = [];
    var dfs = function() {
        if (path.length === n) {
            out.push(path.slice());
            return;
        }
        for (var i = 0; i < n; i++) {
            if (used[i]) continue;
            if (i > 0 && a[i] === a[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            path.push(a[i]);
            dfs();
            path.pop();
            used[i] = false;
        }
    };
    dfs();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Subsets II Medium