A bag holds numbered tokens, and several tokens can carry the same number. Write distinct_selections(nums: list[int]) -> list[list[int]] that returns every different handful you could take out of the bag, from taking nothing to taking everything.
- Two handfuls are the same if they contain the same numbers the same number of times, no matter which physical tokens you grabbed. Return each handful exactly once.
- The handfuls can come back in any order, and the numbers inside each handful in any order.
distinct_selections([2, 1, 2]) # [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]] in some order
distinct_selections([3, 3, 3]) # [[], [3], [3, 3], [3, 3, 3]]
distinct_selections([]) # [[]]
Constraints: 0 <= len(nums) <= 40, -10 <= nums[i] <= 10, and the answer has at most 20,000 handfuls.
With 40 tokens there are 2^40 ways to pick physical tokens, so generating those and removing repeats is far too slow. Aim for time proportional to the total size of the answer.
Show hint
group equal numbers together. For each distinct number, the only real decision is how many copies of it go into the handful: 0, 1, ..., up to its count.