# Time Complexity of Subset Problem

The Subset Exercise taken from LeetCode:

Example: For Input nums = [1,2,3] Return Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]


has as backtrack solution:

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){

The solution has been taken here. I would like to know what the time and space complexities of this solution are. Apparently, the time complexity is O(N * 2^n). The N come from the tempList.add() operation, I have a problem understanding where the 2^N come from.
• Because given a set M, its power set P(M) has a cardinality of 2^|M|, meaning there are 2^|M| subsets to generate. Also note that ArrayList::add is only O(n) in the worst case, it is O(1) amortised. – Emily Nov 10 '19 at 20:20