A shelf display uses a set of coloured blocks, and some blocks are the same colour. Write distinct_orderings(nums: list[int]) -> list[list[int]] that returns every different left-to-right arrangement of all the numbers in nums.
- Equal numbers are interchangeable: swapping two equal numbers doesn't make a new arrangement. Return each arrangement exactly once.
- The arrangements can come back in any order.
distinct_orderings([1, 1, 2]) # [[1, 1, 2], [1, 2, 1], [2, 1, 1]] in some order
distinct_orderings([3, 3]) # [[3, 3]]
distinct_orderings([5]) # [[5]]
Constraints: 1 <= len(nums) <= 12, -10 <= nums[i] <= 10, and the answer has at most 40,000 arrangements.
Twelve numbers have 12! (about 479 million) orderings if you treat them as all different, so producing those and removing repeats is hopeless. Aim for time proportional to the total size of the answer. Don't use itertools.
Show hint
build the arrangement one position at a time, but choose among the distinct values still available (keep a count of each), not among the individual positions of nums.