[PYTHON] Algorithm Gymnastics 24 Subsets

Subsets Specify a set with individual elements to find all that individual subset.

Example

Input: [1, 3] Output: [], [1], [3], [1,3]

Input: [1, 5, 3] Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Solution You can use the breadth-first search (BFS) approach to generate all subsets of the specified set. You can start with an empty set, repeat all the numbers one by one, and add them to the existing set to create a new subset.

As an example, consider [1, 5, 3].

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

Image diagram

Implementation

# Time Complexity: O(2^N) where N is the total number of elements in the input set
# Space Complexity: O(2^N)
def find_subsets(nums):
  subsets = []
  # start by adding the empty subset
  subsets.append([])
  for currentNumber in nums:
    # we will take all existing subsets and insert the current number in them to create new subsets
    n = len(subsets)
    for i in range(n):
      # create a new subset from the existing subset and insert the current element to it
      subset = list(subsets[i])
      subset.append(currentNumber)
      subsets.append(subset)

  return subsets


def main():

  print("Here is the list of subsets: " + str(find_subsets([1, 3])))
  print("Here is the list of subsets: " + str(find_subsets([1, 5, 3])))


main()