The Subset Exercise taken from LeetCode:

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

has as backtrack solution:

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

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);

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.

  • $\begingroup$ 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. $\endgroup$ – Emily Nov 10 '19 at 20:20
  • $\begingroup$ I think a factor O(n) will come from the fact that you are constructing sets which have n/2 elements on average, and constructing sets might not work in constant time. $\endgroup$ – gnasher729 Nov 10 '19 at 22:50
  • $\begingroup$ @Emily if you write a proper answer I will mark it as the right one $\endgroup$ – Giacomo Nov 11 '19 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.