作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
本文详细介绍了五种生成数组子集的方法，包括回溯法、迭代法和位掩码法，提供了代码示例和性能分析，旨在帮助开发者选择最适合的实现方式
题目描述
本题来自Leetcode 78
给你一个整数数组 nums，数组中的元素 互不相同。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入格式
- nums：一个整数数组。
输出格式
- 返回一个列表，其中包含所有可能的子集。
示例
示例 1
输入: nums = [1,2,3] 输出: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
示例 2
输入: nums = [0] 输出: [[],[0]]
方法一：回溯法
解题步骤
- 定义递归函数：使用递归函数
backtrack来生成所有可能的子集。 - 递归选择：从当前位置开始，递归地选择下一个元素加入子集或不加入，直到遍历完数组。
完整的规范代码
def subsets(nums): """ 使用回溯法生成所有可能的子集 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的子集 """ res = [] subset = [] def backtrack(start): res.append(subset.copy()) for i in range(start, len(nums)): subset.append(nums[i]) backtrack(i + 1) subset.pop() backtrack(0) return res # 示例调用 print(subsets([1, 2, 3])) # 输出: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
算法分析
- 时间复杂度：(O(N * 2^N))，其中 (N) 是数组的长度。生成所有子集并复制到输出列表中每个子集需要 (O(N)) 时间。
- 空间复杂度：(O(N))，递归过程中的栈深度最大为 (N)。
方法二：迭代法
解题步骤
- 迭代添加：开始时子集只包含空集，遍历每个数字，将其添加到现有的所有子集中，形成新的子集。
完整的规范代码
def subsets(nums): """ 使用迭代法生成所有可能的子集 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的子集 """ res = [[]] for num in nums: res += [item + [num] for item in res] return res # 示例调用 print(subsets([1, 2, 3])) # 输出: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
算法分析
- 时间复杂度：(O(N * 2^N))，其中 (N) 是数组的长度。每个步骤中，子集的数量加倍。
- 空间复杂度：(O(N * 2^N))，存储所有子集。
方法三：位掩码
解题步骤
- 位掩码表示：每个子集可以由一个长度为 (N) 的位掩码表示，其中 (N) 是数组的长度。位掩码中的每一位表示对应位置的元素是否存在于子集中。
完整的规范代码
def subsets(nums): """ 使用位掩码生成所有可能的子集 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的子集 """ n = len(nums) res = [] for i in range(2 ** n, 2 ** (n + 1)): # 生成位掩码，从 2^n 到 2^(n+1) - 1 bitmask = bin(i)[3:] res.append([nums[j] for j in range(n) if bitmask[j] == '1']) return res # 示例调用 print(subsets([1, 2, 3])) # 输出: [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
算法分析
- 时间复杂度：(O(N * 2^N))，需要 (2^N) 次迭代，每次迭代中构造子集的时间复杂度为 (O(N))。
- 空间复杂度：(O(N * 2^N))，存储所有子集。
方法四：二进制数序列
解题步骤
- 二进制增加：每一个子集可以通过对应的二进制数来表示，通过递增二进制数生成所有可能的子集。
完整的规范代码
def subsets(nums): """ 使用二进制数序列生成所有可能的子集 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的子集 """ res = [] n = len(nums) for i in range(2 ** n): subset = [nums[j] for j in range(n) if (i & (1 << j))] res.append(subset) returnres # 示例调用 print(subsets([1, 2, 3])) # 输出: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
算法分析
- 时间复杂度：(O(N * 2^N))，其中 (N) 是数组的长度。需要 (2^N) 次迭代，每次迭代中构造子集的时间复杂度为 (O(N))。
- 空间复杂度：(O(N * 2^N))，存储所有子集。
方法五：库函数
解题步骤
- 使用库函数：利用 Python 的
itertools模块中的combinations函数来生成所有可能的子集。
完整的规范代码
from itertools import combinations def subsets(nums): """ 使用库函数生成所有可能的子集 :param nums: List[int], 输入的整数数组 :return: List[List[int]], 所有可能的子集 """ res = [] for i in range(len(nums) + 1): for combo in combinations(nums, i): res.append(list(combo)) return res # 示例调用 print(subsets([1, 2, 3])) # 输出: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
算法分析
- 时间复杂度：(O(N * 2^N))，尽管内置函数高效，但基本上还是需要遍历所有可能的组合。
- 空间复杂度：(O(N * 2^N))，需要存储 (2^N) 个子集，每个子集最多含有 (N) 个元素。
不同算法的优劣势对比
| 特征 | 方法一：回溯法 | 方法二：迭代法 | 方法三：位掩码 | 方法四：二进制数序列 | 方法五：库函数 |
| 时间复杂度 | (O(N * 2^N)) | (O(N * 2^N)) | (O(N * 2^N)) | (O(N * 2^N)) | (O(N * 2^N)) |
| 空间复杂度 | (O(N)) | (O(N * 2^N)) | (O(N * 2^N)) | (O(N * 2^N)) | (O(N * 2^N)) |
| 优势 | 易于理解，灵活 | 直接且简单 | 利用位操作效率高 | 直观且容易实现 | 利用成熟的库，代码简洁 |
| 劣势 | 递归可能复杂 | 子集构建重复 | 需理解位操作 | 直接处理二进制较抽象 | 性能依赖库实现，灵活性差 |
应用示例
数据科学：在特征选择中，可以用来生成特征的所有可能组合，帮助分析哪些特征组合对模型效果最好。
机器学习：在进行模型训练之前，可能需要对不同的特征组合进行测试，以确定最有效的特征集。
教学与研究：在算法课程中，可以使用这些方法来教学组合生成的不同技术和优化方法。
这些方法提供了多种生成子集的途径，适用于不同的场景和需求，选择合适的方法可以提高代码效率和可读性。
欢迎关注微信公众号 数据分析螺丝钉
