181. Permutations II

Medium · Backtracking

Given an array of integers that may contain duplicates, return all unique permutations of the array in any order.

A permutation is an arrangement of all elements from the input array. Since the array may have duplicate values, you must avoid generating duplicate permutations.

For example, if the input is [1, 1, 2], there are only 3 unique permutations, not 6, because swapping the two 1's produces the same arrangement.

Examples

Example 1
Input: [1, 1, 2]
Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Explanation: The array has two 1's and one 2. The three unique permutations are listed. Note that [1, 1, 2] and [1, 1, 2] (from swapping the two 1's) are the same, so we only include it once.
Example 2
Input: [0]
Output: [[0]]
Explanation: A single-element array has exactly one permutation: itself.

Constraints