0078.子集
难度：🟡 中等
标签：位运算、数组、回溯
链接：78. 子集
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
解题思路
核心思想
本题的目标是找出给定集合的所有子集（也称为幂集）。对于集合中的每一个元素，我们都有两种选择：选 或 不选。所有这些选择的组合就构成了全部的子集。这是一个典型的组合搜索问题，非常适合使用 回溯法 来解决。
思路选择
回溯法（深度优先搜索 DFS） 是解决此问题的标准思路。我们把生成子集的过程看作是在一棵决策树上进行探索。
我们可以定义一个递归函数，它负责从一个给定的起始位置开始，构建所有可能的子集。
在递归的每一层，我们首先将当前已构建的路径（一个子集）加入结果集，然后遍历后续的元素，将它们逐一加入路径，并递归地进入下一层决策。
关键步骤
定义回溯函数：创建一个递归函数，例如
backtrack(startIndex, path)。startIndex: 表示本次选择应该从nums数组的哪个索引开始，以避免产生重复的组合（如[1,2]和[2,1]）。path: 一个数组，存储当前正在构建的子集。
收集结果：在回溯函数的入口，首先将当前的
path的一个副本加入到最终的结果集results中。因为空集和所有中间过程形成的路径都是有效的子集。循环与递归： a. 从
startIndex开始，循环遍历nums数组。 b. 做出选择：将当前元素nums[i]推入path。 c. 进入下一层决策：以i + 1作为新的起始索引，递归调用回溯函数。 d. 撤销选择：当深层递归返回后，将之前加入的元素从path中弹出 (path.pop())，以便回溯到上一状态，尝试其他的选择分支。
代码实现 (推荐)
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
const results = [];
const path = [];
const backtrack = (startIndex) => {
// 收集子集，每个路径都是一个子集
results.push([...path]);
// 如果起始位置已经超出数组范围，则终止
if (startIndex >= nums.length) {
return;
}
for (let i = startIndex; i < nums.length; i++) {
// 做出选择
path.push(nums[i]);
// 递归探索
backtrack(i + 1);
// 撤销选择
path.pop();
}
};
backtrack(0);
return results;
};
原始代码分析 (用户提供)
您提供的代码是此问题的标准且高效的回溯解法，逻辑完全正确。经过变量名优化后，代码意图更加清晰。
/**
* 优化的回溯辅助函数
* @param {number[]} nums - 原始输入数组
* @param {number[]} currentSubset - 当前正在构建的子集
* @param {number[][]} allSubsets - 最终结果集
* @param {number} startIndex - 本轮选择的起始索引
*/
var backtrack = function (nums, currentSubset, allSubsets, startIndex) {
// 1. 将当前路径作为一个有效子集加入结果
allSubsets.push([...currentSubset]);
// 2. 从指定位置开始遍历，避免产生重复组合
for (let i = startIndex; i < nums.length; i++) {
// 3. 做出选择
currentSubset.push(nums[i]);
// 4. 进入下一层决策
backtrack(nums, currentSubset, allSubsets, i + 1);
// 5. 撤销选择
currentSubset.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function (nums) {
const allSubsets = [];
backtrack(nums, [], allSubsets, 0);
return allSubsets;
};
- 优点：此实现堪称回溯法求子集的模板，逻辑清晰，正确地处理了所有子集的生成和去重。
复杂度分析
时间复杂度：O(n × 2ⁿ) 其中 n 是数组
nums的长度。总共有2ⁿ个子集，对于每个子集，我们都需要 O(k) 的时间来将其复制到结果数组中（k 是子集长度，平均为 n/2）。空间复杂度：O(n) 不考虑存储结果的数组，空间复杂度主要由递归调用栈的深度决定，最深为 n。
相关题目
总结
本题是回溯算法的基石之一，深刻地体现了如何通过递归和“选择-探索-撤销”的模式来系统地构建所有组合解。理解本题的解法是掌握更复杂组合、排列、分割等问题的关键。