Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
nums = [1,2,2][[],[1],[1,2],[1,2,2],[2],[2,2]]nums = [0][[],[0]]Sort brings duplicates together. The skip condition i>start && nums[i]==nums[i-1] prevents choosing the same value twice at the same recursion depth, avoiding duplicate subsets while still allowing the same value at different depths (e.g., [2] and [2,2] are both valid when there are two 2s).
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.
Sort, then skip equal values at the same level. i greater than start is what allows 2, 2 deeper down.
Run the animation above on your own input, or watch the 1:17 video explanation of Subsets II with a dry run and Java code.