Subsets II

Problem

Given an integer array nums that may contain repeated values, return every distinct subset of it. Two subsets are the same if they contain the same values with the same multiplicities, regardless of which original positions were chosen. Output order does not matter.

• Up to 12 elements, which may repeat.
• Each value is between -15 and 15.

Examples

• nums = [3, 5, 5] → [[], [3], [5], [3,5], [5,5], [3,5,5]]. Choosing the first 5 alone or the second 5 alone gives the same subset, counted once.
• nums = [7] → [[], [7]].
• nums = [9, 9, 9] → [[], [9], [9,9], [9,9,9]]. Only the count of 9s matters.

Hints

1. Run the ordinary subsets backtracking on [1, 2, 2] and write down which paths produce the same subset. What do those paths have in common?
2. If equal values sit next to each other, then at any given depth choosing the second copy after skipping the first can only recreate a branch you already explored.
3. Sort, then in the loop skip nums[i] when i > start and nums[i] == nums[i-1].