List every subset of a list that has duplicates, with no repeats. Sort first, then skip a value already tried at the same depth.
▼The problem
LeetCode 90 (Medium). Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The answer must not contain duplicate subsets; any order is fine.
Examples (LeetCode's): [1, 2, 2] → [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]] and [0] → [[], [0]].
The solution
def subsetsWithDup(nums):
nums.sort()
res, path = [], []
def backtrack(start):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return resTranscript
Subsets Two. The numbers may contain duplicates. Return every subset, but never the same one twice. Like Subsets, but with twins.
Take one, two, two. Six subsets: empty, one, one two, one two two, two, and two two. A lone zero gives empty and zero.
The slow way: build all two to the n subsets, then drop repeats with a set of sorted tuples. That's eight built for six kept. The copies were wasted work.
The fix: sort first, so twins hang side by side, like socks on a line. Then backtrack. At each depth, pick any sock from start onward, but if it matches the sock before it and isn't the first choice here, skip it. That value was already tried at this depth.
In code: sort, then record a copy of the path and loop i from start. Skip when i is past start and nums of i equals nums of i minus one. Otherwise append, recurse with i plus one, and pop.
Walk one, two, two. Record empty. Pick one, then two: one two. The next two: one two two. Back at one's depth, the second two is a twin: skip. At the top, pick two, then two two. The last two is a twin at the top: skip. Six subsets, no repeats.
With no duplicates there are two to the n subsets, each copied in up to n steps: order n times two to the n time. The path and call stack take order n space, plus the output.
Sort, skip twins, recurse. That's Subsets Two.