Distinct Orderings With Repeats

Medium

You are given an integer array values that may contain repeated numbers. Return every distinct way to line these numbers up. Two arrangements are the same if every position holds the same number. The arrangements may be listed in any order, but each must appear exactly once.

Example 1

values=[2, 2, 5] → [[2, 2, 5], [2, 5, 2], [5, 2, 2]]

The two 2s are indistinguishable, so there are only three distinct orders: 2 2 5, 2 5 2 and 5 2 2.

Example 2

values=[0, -1] → [[-1, 0], [0, -1]]

Two different numbers give two orders.

Example 3

values=[4, 4, 4] → [[4, 4, 4]]

All numbers are equal, so there is exactly one order.

Constraints

1 ≤ len(values) ≤ 8
-10 ≤ values[i] ≤ 10

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Backtracking Sorting

Similar problems

Picks Without a Fixed Gap Medium Strongest Product Team Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium

Input

values=[2, 2, 5]

Expected

[[2, 2, 5], [2, 5, 2], [5, 2, 2]]

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.