Subsets

MoyenRetour sur trace Manipulation de bits

+10

On te donne une liste nums d’entiers distincts. Retourne tous ses sous-ensembles, y compris l’ensemble vide et la liste complète : n valeurs donnent 2^n sous-ensembles. Écris chaque sous-ensemble avec ses valeurs en ordre croissant et énumère les sous-ensembles dans l’ordre lexicographique : compare deux sous-ensembles valeur par valeur ; la première différence détermine l’ordre, et un sous-ensemble qui est le préfixe d’un autre vient avant celui-ci. Pour [1, 2], la réponse est [[], [1], [1, 2], [2]].

Fonction

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: les valeurs, toutes différentes, dans n’importe quel ordre
Renvoieinteger-2d-array: chaque sous-ensemble, trié par ordre croissant, énuméré dans l’ordre lexicographique

Contraintes

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Toutes les valeurs de nums sont différentes.
nums peuvent apparaître dans n'importe quel ordre.

Exemples

Entrée: nums = [3, 1, 2]
Sortie: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Explication: Une fois triées, les valeurs sont 1, 2, 3, et trois valeurs donnent 2^3 = 8 sous-ensembles. [1, 2] vient avant [1, 2, 3] parce qu’il en est le début, et [1, 2, 3] vient avant [1, 3] parce que 2 est plus petit que 3 à la deuxième position.

Entrée: nums = [0]
Sortie: [[], [0]]
Explication: Un ensemble a deux sous-ensembles : ne pas prendre l’élément et obtenir [], ou le prendre et obtenir [0]. Le sous-ensemble vide vient toujours en premier.

Entrée: nums = [5, -2]
Sortie: [[], [-2], [-2, 5], [5]]
Explication: Les valeurs sont triées en -2 et 5, donc [-2, 5] s’écrit dans cet ordre. Chaque sous-ensemble contenant -2 vient avant [5], car -2 est inférieur à 5.

+13 tests cachés à la soumission

Pour aller plus loin

Peux-tu produire la même liste sans récursion, en construisant chaque sous-ensemble directement à partir du précédent ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Il y a 2^n sous-ensembles, donc aucune méthode ne peut effectuer moins de O(2^n) opérations. La vraie question est de savoir comment produire chaque sous-ensemble une seule fois, dans l’ordre requis, sans trier 1024 listes ensuite. Le retour sur trace des valeurs triées, qui enregistre chaque nœud de l’arbre de décision au fur et à mesure qu’on le visite, parcourt les sous-ensembles exactement dans l’ordre lexicographique.

Masques de bits, puis tri

Intuition

Alignez les valeurs triées aux positions de 0 à n-1. Un sous-ensemble indique oui ou non pour chaque position, et c’est ce que font les n bits d’un nombre. Ainsi, les nombres de 0 à 2^n-1 correspondent aux sous-ensembles : pour [1, 2, 3], le masque 5 est 101 en binaire, les bits 0 et 2 sont activés, et il représente [1, 3]. Le masque 0 est le sous-ensemble vide et le masque 7 est la liste complète.

Des masques différents donnent des sous-ensembles différents, et chaque sous-ensemble a un masque ; la boucle produit donc les 2^n sous-ensembles exactement une fois. Lire les bits en partant de la position 0 et en parcourant les valeurs triées écrit chaque sous-ensemble dans l’ordre croissant.

Les masques ne sortent pas dans l’ordre demandé par le problème. Le masque 1 est [1], le masque 2 est [2] et le masque 3 est [1, 2], donc [2] se retrouverait avant [1, 2]. Pour corriger cela, utilisez un tri dont le comparateur examine les valeurs une par une et place un préfixe en premier. Le tri coûte plus cher que la génération : les 2^n sous-ensembles nécessitent environ n × 2^n comparaisons, et chaque comparaison lit jusqu’à n valeurs. Pour n = 10, cela représente environ 10^5 lectures, ce qui reste rapide, mais c’est un travail que l’approche suivante n’effectue jamais.

Algorithme

Trie nums afin que chaque sous-ensemble soit en ordre croissant.
Pour chaque masque de 0 à 2^n-1, rassemble les valeurs aux positions dont le bit est activé.
Trie la liste des sous-ensembles : à la première position où deux sous-ensembles diffèrent, la plus petite valeur l’emporte et, si l’un se termine en premier, il vient avant l’autre.
Renvoie la liste triée.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Retour sur trace : choisir, explorer, annuler son choix

Intuition

Imagine les sous-ensembles comme un arbre. La racine est le sous-ensemble vide. Sous un nœud, tu peux ajouter n’importe quelle valeur supérieure à la dernière que tu as ajoutée. Pour les valeurs triées [1, 2, 3], la racine a pour enfants [1], [2] et [3] ; [1] a pour enfants [1, 2] et [1, 3] ; [1, 2] a pour enfant [1, 2, 3]. Chaque sous-ensemble apparaît exactement une fois dans cet arbre, car il n’existe qu’une seule façon de l’écrire par ordre croissant, et chaque nœud est une réponse, pas seulement les feuilles.

Le retour sur trace parcourt l’arbre avec une liste partagée, path. Pour descendre vers un enfant, tu choisis : tu ajoutes la valeur. Tu explores : tu appelles récursivement la fonction, et l’assistant enregistre une copie de path dès son arrivée. Puis tu annules ton choix : tu retires la valeur, afin que path revienne au parent et que l’on puisse essayer le frère suivant. Comme chaque nœud est enregistré en y arrivant, un parent est toujours écrit avant ses enfants.

C’est pourquoi la sortie est en ordre lexicographique, sans tri. Les enfants d’un nœud sont essayés de la plus petite valeur à la plus grande, et le parcours termine une branche entière avant d’en commencer une autre. Pour [1, 2, 3], il enregistre [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3] : l’ordre d’un dictionnaire, avec un préfixe avant ses extensions.

L’arbre comporte 2^n nœuds et la copie d’un chemin coûte jusqu’à n, donc le temps d’exécution est O(n × 2^n), soit la taille de la réponse elle-même. En plus de la sortie, tu conserves un chemin et une pile d’appels, tous deux de profondeur maximale n.

Algorithme

Triez les valeurs.
Écrivez explore(start). Elle ajoute d’abord une copie de path au résultat.
Ensuite, pour chaque index i de start jusqu’à la fin : ajoutez values[i] à path (choisir), appelez explore(i+1) (explorer), puis supprimez la dernière valeur (annuler le choix).
Appelez explore(0) avec un chemin vide et renvoyez le résultat.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Pièges et cas limites

La plupart des mauvaises réponses ici sont dues à l’ordre ou au partage d’une même liste.

Ajouter path lui-même au lieu d’une copie. Toutes les entrées pointent alors vers la même liste, qui est vide à la fin du parcours ; tu renvoies donc 2^n copies de [].
Oublier de trier nums. Avec [3, 1, 2], l’arbre construit [3, 1], qui n’est pas en ordre croissant, et le parcours ne suit alors plus l’ordre lexicographique.
Enregistrer uniquement aux feuilles, comme tu le ferais pour les permutations. Chaque nœud de cet arbre est un sous-ensemble ; enregistrer uniquement les chemins qui atteignent la fin renvoie trop peu de sous-ensembles.
Rappeler la fonction avec start+1 au lieu de i+1. Une valeur peut alors suivre une valeur plus grande, ou même se suivre elle-même, et tu obtiens des listes telles que [3, 2] et [3, 3], qui ne sont pas des sous-ensembles en ordre croissant.
Utiliser l’arbre d’inclusion ou d’exclusion (décider pour la valeur 0, puis la valeur 1, et ainsi de suite) et enregistrer les feuilles. Il trouve tous les 2^n sous-ensembles, mais essayer l’inclusion en premier place la liste complète en premier, et essayer l’exclusion en premier place [3] avant [2]. Aucun des deux ordres n’est lexicographique.
Un comparateur qui trie d’abord par longueur donne [], [1], [2], [3], [1, 2], ce qui correspond à un ordre différent.

Questions fréquentes4

Combien de sous-ensembles possède un ensemble de n éléments ?

2^n. Chaque élément est soit inclus, soit exclu, indépendamment des autres, donc les choix se multiplient : deux pour le premier élément, deux pour le deuxième, et ainsi de suite. Trois valeurs donnent 8 sous-ensembles et dix en donnent 1024, en comptant le sous-ensemble vide et l’ensemble complet.

Quelle est la complexité temporelle du problème des sous-ensembles ?

O(n × 2^n). Il y a 2^n sous-ensembles, et en écrire un prend jusqu’à n étapes, donc même renvoyer la réponse coûte autant. Le retour sur trace atteint cette borne et ne nécessite que O(n) espace supplémentaire. La génération avec des masques de bits est tout aussi rapide, mais le tri du résultat ensuite ajoute un facteur n supplémentaire.

Dois-je utiliser le retour sur trace ou des masques de bits pour les sous-ensembles ?

Les masques de bits sont courts, ne nécessitent pas de récursion et rendent le choix d’inclusion ou d’exclusion visible sous forme de bits. Le retour sur trace génère naturellement les sous-ensembles dans l’ordre lexicographique et s’adapte aux variantes courantes : ignorer les valeurs répétées, ne garder que les sous-ensembles de taille k ou uniquement ceux dont la somme atteint une valeur cible, ce qui permet d’arrêter l’exploration d’une branche plus tôt.

Comment gérer les valeurs en double dans les sous-ensembles ?

Triez les valeurs, puis dans la boucle de la fonction auxiliaire de retour sur trace, ignorez une valeur qui est égale à celle qui la précède au même niveau : i > start et values[i] == values[i-1]. La première copie explore déjà tous les sous-ensembles qui l’utilisent ; une branche sœur qui commence par la deuxième copie ne ferait que reconstruire les mêmes sous-ensembles.

Python

def subsets(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [3, 1, 2]

Attendu

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]