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 pytestfrom 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 defaultdictclass 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