本题采用回溯状态空间搜索算法又称“组合树按序枚举法”解决无重复元素数组的幂集生成问题。其核心本质是将幂集的求解转化为高度为 n 的多叉决策树遍历利用传递的起始索引实现强制保序以避免子集重复。当前提供的源码实现了在时间复杂度 O(n * 2^n) 和额外空间复杂度 O(n) 条件下的组合空间全量检索最终走向是精准输出所有可能的子集集合。一、 问题本质与数据模型对于包含 n 个互不相同元素的整数数组 nums其所有可能的子集即幂集的总数为 2^n 个。该问题的求解面临一个核心的物理约束解集中不能包含重复的子集例如 [1, 2] 与 [2, 1] 视作同一个子集。如果在枚举过程中采用盲目的全排列深度探测将会导致严重的元素无序碰撞从而产生大量重复的组合。为了破除由于排列顺序产生的空间对称困局算法引入了“索引递增前向搜索模型”。回溯函数dfs通过引入一个关键的边界指针i限制了当前层级只能从数组的第i个位置开始向后挑选元素。当在第j个位置选中一个元素并压入路径后下一层的递归起点被强制单向推进至j 1。这种物理机制在拓扑上形成了一个只允许“向右看”的单向流动决策链天然消除了元素倒流组合的可能性使得每个子集内部的元素下标在原数组中均呈严格递增排列从而在根源上断绝了子集重复的产生。二、 算法演进对比在解决无重复数组生成幂集的场景中回溯法在内存的利用率及扩展灵活性上表现优异解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷二进制位域映射法O(n * 2^n)O(1)用 0 到 2^n - 1 的掩码整数表示每个元素的选取状态强依赖整型或长整型的位宽若元素个数 n 突破 64 则无法直接映射级联迭代扩容法O(n * 2^n)O(n * 2^n)初始放入空集遍历每个元素时克隆现有所有子集并加入该新元素在迭代推进中需要在堆内存中频繁创建、扩容和持有大量的中间结果集合回溯前向搜索法当前解法O(n * 2^n)O(n)利用深探多叉树枚举空间通过一条全局共享路径回溯复用内存深度依赖运行时系统调用栈若数组规模过大可能导致高额的栈帧开销三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于无条件状态收集机制与for循环驱动的前向步进控制其内部决策分支证明如下1. 状态全量收集分支ans.add(new ArrayList(path));执行在每次进入递归体时无视任何条件直接对当前路径path物理拷贝一份快照并注入最终解集。物理意义多叉决策树上的每一个格点无论是根节点、中间节点还是叶子节点都唯一对应了原数组的一种合法组合形式。因此该操作不设置任何过滤门槛实现了全量组合的无遗漏捕获。2. 前向保序循环for (int j i; j nums.length; j)执行以传入的参数i作为循环的绝对起点进行线性扫描。数学证明当递归深度增加时循环起点j不可能回溯到小于i的历史区间。这意味着在同一个决策分支内所有被选中的元素下标序列j_1, j_2, ... , j_k必然满足j_1 j_2 ... j_k的严格单调递增关系。这种顺序的唯一性在数学上证明了生成组合的唯一性。3. 状态压栈与回溯撤销path.add(...)与path.removeLast();执行先将当前遍历元素送入路径递归完成后立即执行反向弹出。数学证明path在物理上是一个全局共享的独占型局部线性表。当算法完成对以nums[j]为开头的所有深层子集的穷举后通过removeLast()显式擦除该状态使全局路径指针安全回退到当前决策节点的初始配置确保了后续同层兄弟节点nums[j1]的检索不会受到历史残留数据的污染。四、 算法执行状态机步进示例以输入数组nums [1, 2, 3]为例规模 n 3幂集总数 8状态机的演进与解集写入过程如下表所示步骤当前递归起点 i当前循环指针 j (数值)全局共享路径 path 状态触发的解集写入动作 (Snapshot)空间调用栈与回溯状态说明初始0-[]ans.add([])根节点触发空集率先入库。栈: [0]100 (数值: 1)[1]进入新层ans.add([1])压栈选1。栈: [0, 1]211 (数值: 2)[1, 2]进入新层ans.add([1, 2])压栈选2。栈: [0, 1, 2]322 (数值: 3)[1, 2, 3]进入新层ans.add([1, 2, 3])压栈选3。栈: [0, 1, 2, 3]43循环不启动[1, 2, 3]-触及越界边界开始出栈回溯522 (回溯撤销)[1, 2]-弹出3。栈恢复至: [0, 1, 2]611 (回溯撤销)[1]-弹出2。循环推进至 j2 (数值:3)712 (数值: 3)[1, 3]进入新层ans.add([1, 3])压栈选3。栈: [0, 1, 3]800 (回溯撤销)[]-弹出1。主循环推进至 j1 (数值:2)901 (数值: 2)[2]进入新层ans.add([2])依次类推直至生成 [2,3] 与 [3]五、 源码实现import java.util.ArrayList; import java.util.List; class Solution { public ListListInteger subsets(int[] nums) { // 物理开辟独立堆空间用以承载全量合法的子集快照 ListListInteger ans new ArrayList(); // 声明一个全局共享的动态线性表用作决策树路径的状态记录器 ListInteger path new ArrayList(); // 启动深度优先回溯搜索初始化树的根节点检索起点为索引 0 dfs(ans, path, nums, 0); // 返回最终收集完备的幂集集合 return ans; } private void dfs(ListListInteger ans, ListInteger path, int[] nums, int i) { // 核心控制无条件捕获当前路径状态克隆并持久化写入解集中 ans.add(new ArrayList(path)); // 前向单向步进限制循环的起始下标为传入的 i强制截断历史倒流 for (int j i; j nums.length; j) { // 状态变更将当前选中的物理元素压入共享路径末尾 path.add(nums[j]); // 分治递归单向推进决策树深度将下一层的有效搜索范围收缩至 j 1 dfs(ans, path, nums, j 1); // 状态撤销回溯核心动作将刚刚压入的元素弹出还原现场以供同层决策使用 path.removeLast(); } } }六、 复杂度分析1. 时间复杂度O(n * 2^n)分析从拓扑结构上看该回溯算法所遍历的显式决策树共有 2^n 个节点每个节点精确对应一个最终子集。在每一个节点内部算法都需要执行new ArrayList(path)操作来开辟一块全新的堆内存并拷贝路径元素。由于共享路径path的平均物理长度为 n / 2因此该克隆操作的时间开销与 n 呈线性正比关系。结论总的基本原子操作次数为节点数量与单节点克隆开销的乘积最终定性为 O(n * 2^n)。2. 空间复杂度O(n)分析在不计入用于存放最终返回答案的ans集合的前提下算法在运行期间的额外内存消耗来源于两部分一是全局共享的path线性表其内部同时容纳的元素最大数量不超过原数组的长度 n二是系统级方法调用栈的深度在最深探测路径上栈帧中并行并存的函数帧同样受限于树的高度即 n。结论堆内存的动态状态复用机制与调用栈的深度保持同步额外空间复杂度恒定在常数级线性阶 O(n)。