Description
Return all distinct subsets of an integer array that may contain duplicate values. Each occurrence can be used once; repeated subsets must not appear.
Solution
def subsets_with_dup(nums):
values = sorted(nums)
result, path = [], []
def visit(start):
result.append(path.copy())
for i in range(start, len(values)):
if i > start and values[i] == values[i - 1]:
continue
path.append(values[i])
visit(i + 1)
path.pop()
visit(0)
return resultExamples
Example 1
- Input
[[1,2,2]]- Output
[[],[1],[2],[1,2],[2,2],[1,2,2]]
Repeated 2s create new sizes but not duplicate subsets.
Example 2
- Input
[[0]]- Output
[[],[0]]
Two subsets exist.
Example 3
- Input
[[2,2]]- Output
[[],[2],[2,2]]
Only three distinct subsets exist.
Approach
Sort a copy of the array and backtrack over increasing indices. At each recursion depth, skip a value equal to the previous candidate. Record every current path, including the empty path.
Time & space
O(n 2^n) time and O(n) auxiliary space excluding output, where n is the input length; the bound includes sorting and path copies.