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 Screen Shot 2020-08-07 at 21.42.16.png

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()

Recommended Posts

Algorithm Gymnastics 24 Subsets
Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm exercise 6
Algorithm Gymnastics 24 Middle of the Linked List
Python algorithm
Algorithm exercises 13