Sous-ensembles et ensemble des parties
Générez tous les sous-ensembles d’un ensemble par retour arrière et masquage binaire, en gérant les doublons par tri et en ignorant les éléments répétés.
Sous-ensembles et ensemble des parties est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Les sous-ensembles et l’ensemble des parties
L’ensemble des parties d’un ensemble S est la collection de tous les sous-ensembles possibles de S, y compris l’ensemble vide et S lui-même. Un ensemble de n éléments possède exactement 2ⁿ sous-ensembles. Pour [1, 2, 3], les 8 sous-ensembles sont : [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Il s’agit d’un problème combinatoire fondamental, présent dans les questions d’entretien portant sur la recherche de toutes les combinaisons, partitions ou possibilités.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Génération des sous-ensembles par retour arrière
Utilisez le gabarit choisir-explorer-annuler. La décision de conception essentielle consiste, à chaque appel récursif, à ajouter immédiatement le chemin partiel courant aux résultats, avant de choisir d’autres éléments. Ainsi, chaque état — vide, partiel ou complet — est enregistré comme un sous-ensemble valide. Avancez l’indice start afin de ne considérer que les éléments situés à droite du dernier élément choisi, ce qui garantit l’absence de doublons et préserve l’ordre.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Approche par masque de bits
Une autre approche que le retour arrière est le masquage par bits : chaque sous-ensemble correspond à un nombre de n bits, où le bit i égal à 1 signifie que l’élément i est inclus. Parcourez les valeurs de 0 à 2ⁿ - 1 et, pour chaque nombre, extrayez les bits afin de construire le sous-ensemble. Cette méthode est itérative, souvent plus rapide en pratique et très facile à coder. Cependant, elle se généralise moins bien aux problèmes comportant des contraintes, comme une limite de somme.
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differGénération itérative des sous-ensembles
L’approche itérative construit l’ensemble des parties élément par élément. Commencez par [[] ] (l’ensemble vide). Pour chaque nouvel élément, dupliquez tous les sous-ensembles existants et ajoutez-le à chaque copie. Après avoir traité n éléments, le résultat contient les 2ⁿ sous-ensembles. Cette méthode est équivalente au masquage par bits, mais plus lisible pour les personnes qui ne connaissent pas les opérations bit à bit.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Sous-ensembles II : gestion des doublons
Lorsque l’entrée contient des doublons, l’approche naïve génère des sous-ensembles en double. Pour [1, 2, 2], les deux occurrences de 2 produiraient indépendamment [1, 2]. Correction : utilisez sort d’abord sur le tableau, puis ignorez un candidat au niveau courant s’il est égal au candidat précédent au même niveau. Plus précisément, dans la boucle : if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsPourquoi le saut des doublons fonctionne
La condition i > start and nums[i] == nums[i-1] ignore un doublon uniquement au même niveau de récursion (avec le même start). Elle n'empêche pas de sélectionner la même valeur à des profondeurs différentes. Pour [1, 2, 2] : au niveau 0, nous incluons le premier 2 (index 1), puis, au niveau suivant (start=2), nous incluons le deuxième 2 pour former [2, 2]. En revanche, si nous essayions d'inclure à nouveau le deuxième 2 au niveau 0, la condition le détecterait et l'ignorerait.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Sous-ensembles de taille fixe (k-combinaisons)
Générer uniquement des sous-ensembles d'une taille exactement égale à k (LeetCode 77 : Combinaisons) ajoute une condition d'arrêt anticipé : si les éléments restants ne peuvent pas compléter le chemin jusqu'à la taille k, il faut l'élaguer. La condition permettant cet élagage est i > n - (k - len(path)) : s'il ne reste pas suffisamment d'éléments, arrêtez-vous immédiatement. Cela réduit considérablement l'espace de recherche par rapport à la génération de tous les sous-ensembles suivie d'un filtrage.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Applications de l'ensemble des parties
Le schéma de l'ensemble des parties apparaît dans de nombreuses variantes d'entretien : (1) Partition en deux sous-ensembles de même somme — vérifier si la somme d'un sous-ensemble est égale à total/2. (2) XOR maximal de deux sous-ensembles — essayer toutes les paires de sous-ensembles. (3) Coût minimal pour choisir k éléments — énumérer les sous-ensembles de k éléments. Même si l'énumération directe est exponentielle, beaucoup de ces problèmes admettent des solutions par DP une fois leur structure reconnue. Le point de vue de l'ensemble des parties vous aide à identifier l'espace des états, même lorsque vous l'optimisez ensuite.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Vérification de la somme d'un sous-ensemble
La somme d'un sous-ensemble pose la question suivante : un sous-ensemble du tableau a-t-il une somme égale à une cible ? Ce problème peut être résolu par retour arrière (en temps exponentiel) ou par DP (en temps polynomial). La version avec retour arrière est simple, mais devient impraticable pour de grandes entrées. La version DP (tableau booléen dp[target+1]) est l'approche privilégiée lors des entretiens. Comprendre les deux approches vous aide à expliquer le compromis : le retour arrière fournit toutes les solutions, tandis que DP répond efficacement au problème de décision.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueComplexité de l'énumération des sous-ensembles
Générer tous les sous-ensembles a une complexité temporelle incompressible de O(n × 2ⁿ) — 2ⁿ sous-ensembles, chacun ayant une taille moyenne de n/2. Aucun algorithme ne peut faire mieux lorsque tous les sous-ensembles sont demandés. Pour les problèmes qui demandent un seul sous-ensemble possédant une propriété (comme une somme maximale), il faut privilégier la programmation dynamique ou une approche gloutonne. Point essentiel pour les entretiens : demandez-vous toujours si vous devez énumérer tous les sous-ensembles ou simplement déterminer si un sous-ensemble satisfait une condition — la réponse détermine si un temps exponentiel ou polynomial est acceptable.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Comparaison des trois approches
Pour générer tous les sous-ensembles : le retour arrière est l'approche la plus générale — il s'adapte facilement aux doublons et aux contraintes. Le masquage par bits est concis et rapide, mais limité à n ≤ 30 (à cause de la taille des entiers). L'approche itérative est intuitive et évite le surcoût de la récursion. Les trois produisent une sortie de taille O(n × 2ⁿ). Lors d'un entretien, le retour arrière montre que vous comprenez le processus de décision récursif, qui se généralise aux problèmes plus difficiles. Mentionnez les trois approches lorsque vous les comparez.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Vérification rapide
Évaluez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : le retour arrière génère tous les sous-ensembles en ajoutant chaque chemin partiel aux résultats avant de poursuivre l'exploration, les doublons sont gérés en triant les valeurs et en ignorant les valeurs répétées au même niveau de récursion avec la condition i > start and nums[i] == nums[i-1], et le masquage par bits fournit une alternative itérative concise dans laquelle chaque sous-ensemble correspond à un masque binaire unique. Nous allons maintenant aborder les permutations et les combinaisons, des problèmes d'énumération associés mais soumis à des contraintes différentes.
Questions Fréquemment Posées
La leçon « Sous-ensembles et ensemble des parties » est-elle gratuite ?
Oui — le texte complet de « Sous-ensembles et ensemble des parties » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Sous-ensembles et ensemble des parties » ?
Générez tous les sous-ensembles d’un ensemble par retour arrière et masquage binaire, en gérant les doublons par tri et en ignorant les éléments répétés. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Sous-ensembles et ensemble des parties » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Modèle de retour sur trace : choisir, explorer, annuler
- Sous-ensembles et ensemble des parties
- Permutations et combinaisons
- Problème des N reines et propagation des contraintes