Subsets

Question 1

78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Complexity Analysis

Time complexity: O(N X 2 pow n) to generate all subsets and then copy them into output list.

Space complexity:O(N X 2 pow n)
). This is exactly the number of solutions for subsets multiplied by the number NN of elements to keep for each subset.

For a given number, it could be present or absent (i.e. binary choice) in a subset solution. As as result, for N numbers, we would have in total (2 pow N) choices (solutions).

Answer 1

Takeaway:
Need to discuss TC & SC.

Pseudo Code:

1. Start with an empty set: [[]]
2. Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];
3. Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];
4. Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].