All problems

Permutations II

Medium · backtracking

You are given a list nums of integers that may contain repeated values.

Return every distinct way to arrange all the numbers of nums in a row. Two arrangements are the same when they hold the same value at every position, so swapping two equal numbers does not give a new arrangement. Each distinct arrangement must appear exactly once. The arrangements may be returned in any order.

Examples

Example 1

Input: nums = [1, 1, 2]

Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

The two 1s are interchangeable, so only three different rows exist, not six.

Example 2

Input: nums = [1, 2, 3]

Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

With three different numbers there are 3 * 2 * 1 = 6 arrangements.

Example 3

Input: nums = [5, 5]

Output: [[5, 5]]

Constraints