Permutations II
Medium · Backtracking · Array · Backtracking · Sorting
Problem
Given an array nums that may contain repeated values, return every distinct ordering (permutation) of its elements, in any order.
Two orderings that differ only by swapping equal values are the same ordering and must appear once.
Examples
Input: nums = [2,2,3] Output: [[2,2,3],[2,3,2],[3,2,2]]
The 3 can take any of the three positions, and the two 2s fill the other two.
Input: nums = [0,0] Output: [[0,0]]
Both values are equal, so there is only one distinct ordering.
Constraints
- 1 <= len(nums) <= 8
- -10 <= nums[i] <= 10
Approaches
- All orderings, then drop repeats — time O(n · n!), space O(n · n!)
Follow-up
What if you only need the orderings one at a time, in increasing order? Start from the sorted array and repeatedly apply "next permutation": it steps to the next larger ordering in place and naturally skips repeats, with O(1) extra space.
Related problems
Start free on Cariara · Coding problems · System design studio
