Problem

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

A subset of an array is a selection of elements (possibly none) of the array.

The solution set must not contain duplicate subsets. Return the solution in any order.

https://leetcode.cn/problems/subsets-ii/

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Test Cases

1
2
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
([1,2,2], [[],[1],[1,2],[1,2,2],[2],[2,2]]),
([0], [[],[0]]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
res = sol.subsetsWithDup(nums)
res = [sorted(x) for x in res]
res.sort()
expected = [sorted(x) for x in expected]
expected.sort()
assert res == expected

Thoughts

78. Subsets 的进阶版,nums 中可能有重复的元素,但是结果中不能有重复的子集。

problem 78 中,每个数字的词频为 1,只有选中和不选中两种可能。本题因为可能有重复的数字,先统计每个数字的次数。设一个数字 a 的词频为 k,那么子集中可以有 0 个 a、1 个 a、……、k 个 a 共 k + 1 中可能。

用回溯法,对每个数字穷举每种可能下可以得到的所有子集。

时间复杂度 O(2^n),额外的空间复杂度 O(n)

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from collections import defaultdict


class Solution:
def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
counts: dict[int, int] = defaultdict(int)
for num in nums:
counts[num] += 1

counts = list(counts.items())
n = len(counts)
result = []

def backtrack(i: int, subset: list[int]) -> None:
if i == n:
result.append(subset.copy())
return

num, count = counts[i]
for _ in range(count + 1):
backtrack(i + 1, subset)
subset.append(num)

del subset[-count-1:]

backtrack(0, [])
return result