Временная сложность возврата набора мощности (подмножества Leetcode 78) ⇐ JAVA

[Anonymous]

Почему временная сложность генерации набора мощностей данного массива равна O(n * 2^n). Решение, которое я создал, или даже решение, которое используется в leetcode, запускается 2^n раз. 1 цикл для создания 1 подмножества.
Я также проверил количество запусков, и оно всегда соответствует 2^n. Решение приведено ниже, и в коде также упоминается временная сложность решения как O(n * 2^n). Не могу понять, как это возможно.

Код: Выделить всё

class Solution {

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

public void backtrack(int first, ArrayList 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 subsets(int[] nums) {
n = nums.length;
ArrayList currCombo = new ArrayList();
backtrack(0, currCombo, nums); // One call generates all subsets
return output;
}
}

Теперь, если вы отследите, сколько раз запускался "System.out.println("runstatus: "+(runStatus++));", он всегда будет O(2^n).
Пожалуйста, проясните, что я неправильно интерпретирую?

Подробнее здесь: https://stackoverflow.com/questions/793 ... 78-subsets