Subsets II

Problem

Analytics pipelines enumerate all feature subsets to find the combination that best explains a metric, but duplicate features in the input must not produce duplicate feature sets in the output. Given an integer array that may contain duplicates, return all possible subsets without any duplicate subsets. Sort the input first; at each recursion depth, skip a candidate if it has the same value as the previous candidate at the same depth.

Input: [1, 2, 2]
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
 
Input: [0]
Output: [[], [0]]

Solution

Approach: Subset generation plus a sort and a same-depth duplicate skip.

The skeleton is identical to plain Subsets - record path[:] at entry, loop from start, append, recurse with i + 1, pop. The only addition is nums.sort() up front and the guard if i > start and nums[i] == nums[i - 1]: continue. Sorting clusters equal values so a duplicate is always adjacent to its twin. The guard then says: at any one depth (one loop level), use a given value only the first time you see it. The i > start part is the subtle bit - i == start is the first candidate at this depth, always allowed; i > start with nums[i] == nums[i-1] means this value was already tried as a sibling at this same depth, so skipping it prevents two branches that would build identical subsets. It is critical that the guard is relative to start, not 0: a repeated value picked at a deeper level (as part of [2, 2]) is legitimate, and i > 0 would wrongly suppress it. Trace [1, 2, 2]: at the root, i=1 picks the first 2 to start [2] and [2, 2], but i=2 is skipped because nums[2] == nums[1] and 2 > start=0 - so [2] is produced exactly once.

Edge cases: All-equal input like [2, 2, 2] collapses to one subset per count ([], [2], [2,2], [2,2,2]). The empty set is still recorded on the first call.

Complexity: O(n * 2^n) time, O(n) space - worst case (all distinct) is the full power set; the skip only shrinks the real output.