难度: Medium
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
Submission
运行时间: 32 ms
内存: 15.2 MB
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort()
def backtrace(path, start):
result.append(list(path))
if len(path) == len(nums):
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrace(path, i+1)
path.pop()
backtrace([], 0)
return result
Explain
这个题解使用了回溯算法来生成所有可能的子集。首先将数组进行排序，以方便去除重复的子集。然后定义一个回溯函数，通过维护一个路径数组 path，依次将数组中的元素加入路径中，并递归调用回溯函数，直到达到终止条件。在递归过程中，通过判断当前元素是否与前一个元素相同，来避免生成重复的子集。最后返回所有生成的子集。
时间复杂度: O(n * 2^n)
空间复杂度: O(n * 2^n)
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []
nums.sort() # 对数组进行排序
def backtrace(path, start):
result.append(list(path)) # 将当前路径加入结果集
if len(path) == len(nums): # 达到终止条件
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: # 去除重复的子集
continue
path.append(nums[i]) # 将当前元素加入路径
backtrace(path, i+1) # 递归调用回溯函数
path.pop() # 回溯，移除当前元素
backtrace([], 0) # 调用回溯函数
return result
Explore
当数组nums被排序后，相同的元素会被放置在连续的位置。在回溯过程中，通过比较当前元素nums[i]与其前一个元素nums[i-1]，可以判断当前元素是否与前一个元素相同。如果相同，并且不是循环的起始元素（即i > start），则跳过当前元素，从而避免生成与前一次递归相同的子集。这种方法有效地利用了排序后元素顺序的特性，以简单且有效的方式防止了重复子集的生成。
实际上，终止条件len(path) == len(nums)并不是必须的，因为回溯过程在每次递归时都已经将当前path添加到结果集中。该条件似乎是多余的，因为当path长度与nums相等后，循环不会再继续执行（因为i的范围会超出nums的长度），自然就不会再有递归调用。因此，这个条件可以被移除，而不影响算法的正确性或性能。
参数i+1确保了每次递归调用开始探索的是当前元素的下一个元素，从而生成所有可能的子集组合。这是回溯算法避免重复使用相同元素的关键机制。通过从i+1开始，算法确保了在当前递归层级中，之前已使用的元素不会再次被考虑，从而能生成所有不同的组合而不重复。
在path.pop()操作后没有必要再次检查重复元素，因为重复的检查已经在循环的开始处通过比较nums[i]与nums[i-1]实现。当path.pop()移除最后一个元素后，回溯将继续尝试下一个可能的元素（如果存在）。因为数组已经排序，重复的元素会被前面的逻辑处理掉，不会在后续的递归中产生重复的子集。这确保了算法的效率和简洁性。