[PYTHON] Algorithmus Gymnastik 24 Teilmengen

Subsets Geben Sie eine Menge mit einzelnen Elementen an, um die gesamte einzelne Teilmenge zu finden.

Beispiel

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 Sie können den BFS-Ansatz (Width Priority Search) verwenden, um alle Teilmengen der angegebenen Menge zu generieren. Sie können mit einer leeren Menge beginnen, alle Zahlen einzeln wiederholen und zur vorhandenen Menge hinzufügen, um eine neue Teilmenge zu erstellen.

Betrachten Sie als Beispiel [1, 5, 3].

1. Beginnen Sie mit einem leeren Satz: [[]]
2. Fügen Sie allen vorhandenen Teilmengen die erste Nummer (1) hinzu, um eine neue Teilmenge zu erstellen. [[], [1]]
3. Fügen Sie allen vorhandenen Teilmengen eine zweite Zahl (5) hinzu: [[], [1], [5], [1,5]]
4. Fügen Sie allen vorhandenen Teilmengen die dritte Zahl (3) hinzu: [[], [1], [5], [1,5], [3], [1,3], [5]. , 3], [1,5,3]]

Bilddiagramm

Implementierung

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