作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。

输入格式

• nums：一个整数数组，可能包含重复元素。

输出格式

• 返回所有可能的子集列表。

示例

示例 1

输入: nums = [1,2,2]
输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

---

方法一：回溯法

解题步骤

1. 排序：首先对数组进行排序，以方便处理重复元素。
2. 递归构建：使用递归方法，针对每个元素选择“使用”或“不使用”，并跳过重复元素。

完整的规范代码

def subsetsWithDup(nums):
    """
    使用回溯法生成所有可能的子集，处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()  # 排序以方便处理重复元素
    results = []
    def backtrack(start, path):
        results.append(path[:])  # 添加当前子集
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue  # 跳过重复元素
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return results

# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

算法分析

• 时间复杂度：(O(2^n * n))，其中 (n) 是数组长度。每个元素有选择和不选择两种状态，因此时间复杂度为指数级。每次添加子集到结果中的时间复杂度为 (O(n))。
• 空间复杂度：(O(n))，递归栈的深度最多为 (n)。

方法二：迭代法

解题步骤

1. 迭代构建：从空集开始，每次迭代添加一个新元素到所有已存在的子集中，形成新的子集，并注意处理重复元素。

完整的规范代码

def subsetsWithDup(nums):
    """
    使用迭代法生成所有可能的子集，处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    start, end = 0, 0
    for i in range(len(nums)):
        start = 0
        # 如果当前数字和前一个数字相同，则只在上一轮新加入的子集基础上追加
        if i > 0 and nums[i] == nums[i-1]:
            start = end + 1
        end = len(results) - 1
        for j in range(start, len(results)):
            results.append(results[j] + [nums[i]])
    return results

# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

算法分析

• 时间复杂度：(O(2^n * n))，每个元素可能会导致结果翻倍，需要遍历并复制现有的所有子集。
• 空间复杂度：(O(2^n))，存储所有的子集。

方法三：位掩码法

解题步骤

1. 位掩码生成：利用位掩码的方法生成所有可能的组合。
2. 去重处理：对于生成的每个组合，检查是否是重复的，若不是则添加到结果集中。

完整的规范代码

def subsetsWithDup(nums):
    """
    使用位掩码法生成所有可能的子集，并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = []
    seen = set()
    n = len(nums)
    for i in range(1 << n):  # 从 0 到 2^n - 1
        subset = []
        for j in range(n):
            if i & (1 << j):  # 检查第 j 位是否为 1
                subset.append(nums[j])
        # 转换成元组检查是否重复
        subset_tuple = tuple(subset)
        if subset_tuple not in seen:
            seen.add(subset_tuple)
            results.append(subset)
    return results

# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

算法分析

• 时间复杂度：(O(2^n * n))，位掩码方法生成所有可能的子集，并对每个子集进行处理。
• 空间复杂度：(O(2^n))，用于存储结果和用于查重的集合。

方法四：字典树（Trie）技术

解题步骤

1. 构建字典树：为数组中的每个元素构建一个字典树，以存储所有可能的子集组合。
2. 遍历字典树：遍历字典树以生成所有唯一的子集。

完整的规范代码

这个方法在实际应用中比较复杂，通常不推荐用于这种类型的问题，因为它过于复杂，适合处理更具体的、需要快速查找和插入的场景。因此，这里不提供具体代码实现，而是保持理论上的探讨。

方法五：动态规划

解题步骤

1. 初始化动态表：以空集开始，逐步添加元素。
2. 处理重复元素：对于重复元素，仅在上一次新增的子集中添加，防止产生重复的子集。

完整的规范代码

def subsetsWithDup(nums):
    """
    动态规划法生成所有可能的子集，并处理重复元素
    :param nums: List[int], 输入的整数数组
    :return: List[List[int]], 所有可能的子集
    """
    nums.sort()
    results = [[]]
    last_count = 0
    for i in range(len(nums)):
        start = last_count if i > 0 and nums[i] == nums[i-1] else 0
        last_count = len(results)
        results += [r + [nums[i]] for r in results[start:]]

    return results

# 示例调用
print(subsetsWithDup([1,2,2]))  # 输出: [[], [1], [1,2], [1,2,2], [2], [2,2]]

算法分析

• 时间复杂度：(O(2^n))，每次迭代都会根据当前结果数量添加新的子集。
• 空间复杂度：(O(2^n))，存储所有生成的子集。

不同算法的优劣势对比

特征	方法一：回溯法	方法二：迭代法	方法三：位掩码法	方法四：字典树技术	方法五：动态规划
时间复杂度	(O(2^n * n))	(O(2^n * n))	(O(2^n * n))	高于 (O(2^n))	(O(2^n))
空间复杂度	(O(n))	(O(2^n))	(O(2^n))	可能非常高	(O(2^n))
优势	直观，易于理解	简单易实现	高效，直接	高效查找和插入	高效，易于实现
劣势	可能栈溢出	结果存储消耗大	需要额外处理重复	过于复杂	需要处理重复元素

应用示例

这些方法在处理涉及到组合生成的问题时非常有用，例如在权限管理系统中生成角色的权限组合、在统计学中用于数据分析的各种组合情况生成等。