Why the time complexity of generating power set of given array is O(n * 2^n). The solution which I created or even the solution which is shared on leetcode runs 2^n times. 1 loop to generate 1 subset. I tested the run count as well and it is always meeting 2^n. The solution is given below and the leetcode also mentions the time complexity of their solution as O(n * 2^n). Cant figure out how it is possible.

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

Now, if you track how many times the "System.out.println("runstatus is : "+(runStatus++));" has run, it will always be O(2^n). Please throw some light on this, what I am interpreting incorrectly?

Why the time complexity of generating power set of given array is O(n * 2^n). The solution which I created or even the solution which is shared on leetcode runs 2^n times. 1 loop to generate 1 subset. I tested the run count as well and it is always meeting 2^n. The solution is given below and the leetcode also mentions the time complexity of their solution as O(n * 2^n). Cant figure out how it is possible.

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

Now, if you track how many times the "System.out.println("runstatus is : "+(runStatus++));" has run, it will always be O(2^n). Please throw some light on this, what I am interpreting incorrectly?

• java
• algorithm
• data-structures
• subset
• backtracking

1 Answer 1

The factor