This time the array may contain duplicates. Return all subsets, without repeating any subset.
DSA Animator › DSA Revision › Backtracking › Subsets II
Remember: sort, then skip equal values at the same level. i greater than start is what allows 2, 2 deeper down. The video solves Subsets II (LeetCode 90, Medium) with the Backtracking + Skip Duplicates pattern from the Backtracking topic, and you can replay every step in the interactive Subsets II animation.
This time the array may contain duplicates. Return all subsets, without repeating any subset.
For 1, 2, 2, there are 6 unique subsets. They are the empty set, 1, then 1, 2, then 1, 2, 2, then 2, and 2, 2.
Generating all subsets and removing duplicates with a set wastes work. It is better never to build a duplicate at all.
Sort the array, so equal numbers sit next to each other. Inside one loop level, skip a number if it equals the one just before it. Equal numbers can still be picked one after another deeper in the tree, like 2, 2.
Record the empty set, then go to 1, then 1, 2, then 1, 2, 2. Back at 1, the second 2 equals the first one at the same level, so skip it. Back at the empty set, take 2, and then 2, 2. The second 2 at the top level is a duplicate start, so skip it too. That leaves exactly 6 subsets.
In code, sort the numbers first. In the loop, continue if i is greater than start and the number equals the previous one. Otherwise choose, recurse and un-choose as before, so it's O of n times 2 to the n.
Remember: sort, then skip equal values at the same level. i greater than start is what allows 2, 2 deeper down.