LeetCode 78子集问题：为何幂集生成时间复杂度是O(n*2^n)？

你统计的print语句执行次数确实是O(2^n)，但这只是算法中循环迭代的次数，并非整个算法的全部时间开销，这就是你和LeetCode标注结果有差异的核心原因。

关键在于你忽略了两个主导时间成本的操作：

• 子集复制操作：每次调用backtrack时都会执行output.add(new ArrayList(curr));，这行代码会把当前的curr列表完整复制一份存入结果集。总共有2^{n个子集，而所有子集的元素总数是`n*2^(n-1)`（每个元素会出现在一半的子集里），所以复制所有子集的总时间是O(n*2}n)。
• 元素的添加与移除：回溯过程中，每个元素会被加入curr和从curr移除各2^{(n-1)次（对应包含该元素的所有子集），n个元素的总操作次数也是`n*2^(n-1)`，量级同样是O(n*2}n)。

时间复杂度的计算要覆盖所有操作的总开销，而非只看某一条语句的执行次数。上述两个操作的时间成本主导了整个算法的复杂度，所以最终结果是O(n*2^n)。

附上你的解法代码：

class Solution {

    private List<List<Integer>> output = new ArrayList();
    private int n;
    private int runStatus=0;

    public void backtrack(int first, ArrayList<Integer> curr, int[] nums) {
        // Add the current subset to the output
        output.add(new ArrayList(curr));
        // Generate subsets starting from the current index
        for (int i = first; i < n; ++i) {
            curr.add(nums[i]);
            System.out.println("runstatus is : "+(runStatus++));
            backtrack(i + 1, curr, nums);
            curr.remove(curr.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        ArrayList<Integer> currCombo = new ArrayList<Integer>();
        backtrack(0, currCombo, nums); // One call generates all subsets
        return output;
    }
}

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