I would like to verify the space and time complexity of my solution to subsets problem on leetcode. The space complexity is O(N) due to stack space. The time complexity is O(2^N) as the work on each ith level is adding 2^i elements to the list. So summing 2^i from 0 to N yields O(2^N). Am I correct? I am not sure because the 3 official solutions have time complexity O(N*2^N).

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // Space Complexity: O(N) 
    // Time Complexity: 2^0   2^1   ...   2^N = O(2^N) 
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(List.of());
        subsetsHelper(nums, 0, subsets);
        return subsets;
    }

    private void subsetsHelper(int[] nums, int index, List<List<Integer>> subsets) {
        if (index >= nums.length) return;
        int current = nums[index];
        int initialSize = subsets.size();
        for (int i = 0; i < initialSize; i  ) {
            var list = subsets.get(i);
            var listCopy = new ArrayList<>(list);
            listCopy.add(current);
            subsets.add(listCopy);
        }
        subsetsHelper(nums, index   1, subsets);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.subsets(new int[]{0, 1, 2}));
    }

}

CodePudding user response：

I figured out why it's 2^N times N.

For subsetsHelper(), at ith level, the number of subsets is 2^(i-1). And the size of each subsetList in it is O(N). As I double the size of each sub subsetList (from list to listCopy in code) in subsetsHelper() its time complexity is O(N*2^i).

And since the function is called N times, the time complexity of subsets() is O(N*(2^0 ... 2^(N-1)) = O(N*2^N)