[PYTHON] Gymnastique algorithmique 24 sous-ensembles

Subsets Spécifiez un ensemble avec des éléments individuels pour trouver tout ce sous-ensemble individuel.

Exemple

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 Vous pouvez utiliser l'approche de recherche de priorité de largeur (BFS) pour générer tous les sous-ensembles de l'ensemble spécifié. Vous pouvez commencer avec un ensemble vide, répéter tous les nombres un par un et les ajouter à l'ensemble existant pour créer un nouveau sous-ensemble.

À titre d'exemple, considérons [1, 5, 3].

1. Commencez avec un ensemble vide: [[]]
2. Ajoutez le premier numéro (1) à tous les sous-ensembles existants pour créer un nouveau sous-ensemble. [[], [1]]
3. Ajoutez un deuxième numéro (5) à tous les sous-ensembles existants: [[], [1], [5], [1,5]]
4. Ajoutez le troisième numéro (3) à tous les sous-ensembles existants: [[], [1], [5], [1,5], [3], [1,3], [5] , 3], [1,5,3]]

Diagramme d'image

la mise en oeuvre

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