LeetCode 含重複元素的子集：迭代去重生成所有子集

題目描述

給定可能包含重複元素的整數數組，返回所有可能的子集（冪集）。解集不能包含重複子集，子集內元素非降序。

迭代去重思路

先排序。維護結果集 res。遍歷數組，對於重複元素，只在上一輪新增的子集基礎上添加當前元素（即從 start 索引開始），避免生成重複子集。用 temp_size 記錄上一輪結果集大小。

代碼實現 (Python)

class Solution:
    def subsetsWithDup(self, nums):
        res = [[]]
        nums.sort()
        temp_size = 0
        for i, num in enumerate(nums):
            start = temp_size if i > 0 and num == nums[i-1] else 0
            temp_size = len(res)
            for j in range(start, temp_size):
                res.append(res[j] + [num])
        return res

複雜度

• 時間：O(n * 2^n)
• 空間：O(n * 2^n)