LeetCode 第 78 题：子集（Subsets） 题目描述 给定一个整数数组 nums ，数组中的元素互不相同。要求返回所有可能的子集（幂集）。解集不能包含重复的子集，且可以按任意顺序返回。 示例： 输入： nums = [1,2,3] 输出： [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 解题过程 第一步：理解子集的性质 子集是原数组中元素的任意组合，包括空集和全集。 若数组长度为 n ，则子集总数是 2^n （每个元素可选或不选）。 需要避免重复，因题目保证元素互不相同，故直接递归生成即可。 第二步：暴力回溯（递归搜索） 回溯法是直观的解法，通过递归枚举所有选择路径。 核心思路： 从空集开始，逐步添加元素。 每层递归决定是否加入当前元素，并进入下一层。 使用 start 参数避免重复组合（如 [1,2] 和 [2,1] 被视为重复）。 步骤分解： 初始化结果列表 res = [] ，临时路径 path = [] 。 定义回溯函数 backtrack(start, path) ： 将当前 path 加入 res （记录所有中间状态）。 遍历 start 到数组末尾的索引 i ： 将 nums[i] 加入 path 。 递归调用 backtrack(i + 1, path) （避免重复使用元素）。 回溯：从 path 移除 nums[i] 。 调用 backtrack(0, []) 并返回 res 。 示例推导（ nums = [1,2,3] ）： 初始： path = [] → 加入 res ： [[]] 第一层递归（ start=0 ）： 选 1 ： path = [1] ，加入 res → [[], [1]] 递归（ start=1 ）：选 2 → [1,2] ，加入 res ；再递归选 3 → [1,3] 。 回溯到 1 后不选，继续选 2 → [2] ，同理生成 [2,3] 。 选 3 → [3] 。 最终得到所有 8 个子集。 第三步：迭代法（位运算思想） 由于每个元素有“选”或“不选”两种状态，可用二进制位表示选择情况。 核心思路： 用 0 到 2^n - 1 的二进制数表示所有子集。 二进制位 1 对应选取该元素。 步骤分解： 计算 n = len(nums) ，子集数 total = 2^n 。 遍历 i 从 0 到 total - 1 ： 初始化当前子集 subset = [] 。 遍历 j 从 0 到 n-1 ： 检查 i 的第 j 位是否为 1 （通过 (i >> j) & 1 判断）。 若是，将 nums[j] 加入 subset 。 将 subset 加入结果列表。 返回结果。 示例（ nums = [1,2,3] ）： i=0 （二进制 000 ）→ [] i=1 （ 001 ）→ [1] i=2 （ 010 ）→ [2] i=3 （ 011 ）→ [1,2] ...直到 i=7 （ 111 ）→ [1,2,3] 第四步：复杂度分析 时间复杂度： O(n * 2^n) 。共有 2^n 个子集，每个子集平均长度 n/2 ，生成需 O(n) 。 空间复杂度： O(n) （递归栈或临时路径）。 总结 回溯法 ：通用性强，易于理解，适合逐步构建解。 位运算法 ：利用二进制特性，代码简洁，但需理解位操作。 两种方法均能高效解决子集问题，回溯法更常用于面试讲解。