GoCalf Calf 的自留地 · 昙花一现

90. Subsets II

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

python
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
solution_test.py下载完整源码
py
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

py
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

评论需要 JavaScript。