使用回溯法生成所有唯一子集的时间与空间复杂度咨询

你的推导结论是正确的，这段回溯实现的时间、空间复杂度均为 O(n×2^n)，以下是详细推导过程：

时间复杂度推导 #

我们可以从两个角度验证这个结论：

• 首先明确基础事实：n个不同元素的所有子集总数为 2^n，每个元素恰好会出现在 2^(n-1) 个子集中，因此所有子集的元素总个数为 n×2^(n-1)，量级等价于 O(n×2^n)。
• 再看代码核心开销：你代码中最大的时间开销来自 temp.addAll(listSoFar) 操作，单次操作的时间成本和当前 listSoFar 的长度成正比。每个非空子集在生成过程中，每添加一个元素都会触发一次列表复制，复制的总开销恰好等于该子集的长度。把所有子集的生成开销累加，总开销就是所有子集的元素总个数，也就是 O(n×2^n)。

外层遍历子集长度的循环、递归调用的基础开销和上述核心开销相比都可以忽略，因此整体时间复杂度为 O(n×2^n)。

另外纠正你注释里的一个小错误：temp.addAll(listSoFar) 单次的时间复杂度是 当前列表长度，最大为 O(n)，不是 O(2^n)；你之前认为“递归方法总共被调用n次”的认知也有偏差，递归总调用次数是 O(2^n) 量级，但这不影响最终复杂度计算结果。

空间复杂度推导 #

空间复杂度同样为 O(n×2^n)，核心来自两部分：

• 结果集存储：你最终返回的 result 中存储了所有 2^n 个子集，所有子集的总元素数为 n×2^(n-1)，这部分空间开销为 O(n×2^n)。
• 递归栈与中间临时列表：递归调用的最大深度为n（生成最长的全元素子集时的调用栈深度），这部分 O(n) 的开销和结果集相比可以忽略；所有中间生成的 temp 列表最终都会存入结果集，没有额外的重复空间开销。

因此整体空间复杂度为 O(n×2^n)。

内容的提问来源于stack exchange，提问作者Ufder