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

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

Recommended Posts

Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Exercice d'algorithme 6
Gymnastique algorithmique 24 Milieu de la liste liée
Algorithme Python
Exercices d'algorithme 13