Zeitkomplexität des zurückkehrenden Leistungssatzes (Leetcode 78 Teilsätze) ⇐ Java

[Guest]

Warum die zeitliche Komplexität der Erzeugung des Leistungssatzes eines bestimmten Arrays O(n * 2^n) ist. Die Lösung, die ich erstellt habe, oder sogar die Lösung, die auf Leetcode geteilt wird, wird 2^n Mal ausgeführt. 1 Schleife, um 1 Teilmenge zu generieren.
Ich habe auch die Laufanzahl getestet und sie erfüllt immer 2^n. Die Lösung ist unten angegeben und der Leetcode erwähnt auch die zeitliche Komplexität ihrer Lösung als O(n * 2^n). Ich kann nicht herausfinden, wie das möglich ist.

Code: Select all

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;
}
}

Wenn Sie nun nachverfolgen, wie oft „System.out.println(“runstatus is : „+(runStatus++));“ ausgeführt wurde, wird dies immer der Fall sein O(2^n).
Bitte werfen Sie etwas Licht ins Dunkel. Was interpretiere ich falsch?