1
$\begingroup$

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){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[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.

$\endgroup$
  • $\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.