leetcode 78.子集

题解78.子集 (Subsets)1. 题目描述给定一个不含重复元素的整数数组nums返回该数组所有可能的子集幂集。要求解集不能包含重复的子集。你可以按任意顺序返回解集。示例输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]2. 解题思路回溯算法 (Backtracking)本题是经典的组合问题适合使用回溯算法解决。回溯算法的核心思想是“做选择” - “递归探索” - “撤销选择”。我们可以把寻找子集的过程想象成遍历一棵决策树根节点空集[]。分支对于每个位置我们有两个选择选当前数字加入路径。不选当前数字通过循环跳过或回溯实现。叶子节点当没有更多数字可选时到达路径终点。核心逻辑拆解在代码中我们通过backtrack函数模拟这个过程记录结果每次进入backtrack函数当前的路径curr都是一个合法的子集直接加入结果集result。注意这里需要拷贝数组[...curr]因为curr是引用类型后续会被修改。遍历选择从start索引开始遍历nums。start参数的作用保证不重复选择之前的元素且避免生成重复子集如[1,2]和[2,1]视为同一个。做选择 (Push)将nums[i]加入当前路径curr。递归深入调用backtrack(i 1, curr)。传入i 1表示下一层只能从当前元素的后面开始选防止回头选造成重复。撤销选择 (Pop) —— 关键步骤递归返回后必须执行curr.pop()。目的将状态恢复到“做选择之前”以便在同一层级尝试下一个数字即换一条路走。原理这就是“回溯”的含义——退回到上一步重新选择。3. 代码实现 (JavaScript)/** * param {number[]} nums * return {number[][]} */varsubsetsfunction(nums){constresult[];/** * 回溯函数 * param {number} start - 当前遍历的起始索引 * param {number[]} curr - 当前路径正在构建的子集 */functionbacktrack(start,curr){// 1. 前序位置将当前路径加入结果集// 注意必须使用 [...curr] 进行浅拷贝否则 result 中存储的都是同一个引用result.push([...curr]);// 2. 遍历选择列表for(letistart;inums.length;i){// --- 做选择 ---curr.push(nums[i]);// --- 递归进入下一层 ---// i 1 确保不会重复使用当前元素也不会回头选前面的元素backtrack(i1,curr);// --- 撤销选择 (回溯) ---// 关键点移除最后一个元素回到上一层状态以便尝试下一个 icurr.pop();}}// 从索引 0 开始初始路径为空backtrack(0,[]);returnresult;};4. 复杂度分析假设数组长度为N NN。时间复杂度:O ( N ⋅ 2 N ) O(N \cdot 2^N)O(N⋅2N)一个长度为N NN的数组其子集总数为2 N 2^N2N个。构建每个子集拷贝数组平均需要O ( N ) O(N)O(N)的时间。总时间 子集数量× \times×构建成本 2 N × N 2^N \times N2N×N。空间复杂度:O ( N ) O(N)O(N)主要消耗在递归栈的深度。最坏情况下递归深度为N NN例如路径[1, 2, ..., N]。注如果不计算存储结果result所需的空间仅计算算法运行时的额外空间则为O ( N ) O(N)O(N)。如果算上结果集则是O ( N ⋅ 2 N ) O(N \cdot 2^N)O(N⋅2N)。5. 常见疑问解答 (QA)Q1: 为什么要用[...curr]而不是直接result.push(curr)A: JavaScript 中数组是引用类型。curr在整个递归过程中是同一个数组对象。如果不拷贝result里存的都是指向curr的指针。当递归结束curr最终会变成空数组[]那么result里所有的子集都会变成[]。使用[...curr]创建了一个新的副本锁定了当前的状态。Q2:curr.pop()到底是在什么时候执行的A: 它是在递归调用返回之后立即执行的。想象你走进一个房间递归做完事情出来后必须把门关上pop恢复原状才能去进下一个房间。如果你走了 3 步深push 了 3 次返回时就会依次执行 3 次 pop一步步退回到起点。Q3: 为什么循环要从start开始而不是从0开始A: 为了避免重复组合和顺序不同但内容相同的子集。如果从0开始会生成[1, 2]和[2, 1]这在子集问题中被视为重复。限制i start保证了我们只向后看不回头从而天然去重并保持有序。6. 总结这道题是回溯算法的模板题。掌握它的关键在于理解递归树的结构每一层代表做一个选择。状态重置push和pop必须成对出现像括号一样包裹递归调用。剪枝/去重通过start参数控制搜索范围。只要理解了“前进做选择后退撤选择”这一核心逻辑就能轻松解决类似的组合、排列、子集问题。