Sottoinsiemi e insieme delle parti
Generi tutti i sottoinsiemi di un insieme usando il backtracking e le maschere di bit, gestendo i duplicati ordinando gli elementi e saltando quelli ripetuti.
Sottoinsiemi e insieme delle parti è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Sottoinsiemi e insieme delle parti
L'insieme delle parti di un insieme S è la raccolta di tutti i possibili sottoinsiemi di S, compresi l'insieme vuoto e S stesso. Un insieme di n elementi ha esattamente 2ⁿ sottoinsiemi. Per [1, 2, 3], gli 8 sottoinsiemi sono: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Questo è un problema combinatorio fondamentale, che ricorre nelle domande di colloquio sulla ricerca di tutte le possibili combinazioni, partizioni o scelte.
# 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: 16Generazione dei sottoinsiemi con backtracking
Utilizzi il modello scegli-esplora-annulla la scelta. La decisione progettuale fondamentale è questa: a ogni chiamata ricorsiva, aggiunga il percorso parziale corrente ai risultati immediatamente (prima di scegliere altri elementi). In questo modo ogni stato — vuoto, parziale e completo — viene registrato come sottoinsieme valido. Faccia avanzare l'indice start in modo da considerare solo gli elementi a destra dell'ultimo elemento scelto, evitando duplicati e preservando l'ordine.
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]]Approccio con maschere di bit
Un'alternativa al backtracking è l'uso delle maschere di bit: ogni sottoinsieme corrisponde a un numero di n bit, in cui il bit i impostato a 1 indica che l'elemento i è incluso. Si scorra da 0 a 2ⁿ - 1 e, per ogni numero, si estraggano i bit per costruire il sottoinsieme. È un approccio iterativo, spesso più veloce nella pratica e molto semplice da implementare. Tuttavia, non si adatta altrettanto bene ai problemi con vincoli (come un limite sulla somma).
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 differGenerazione iterativa dei sottoinsiemi
L'approccio iterativo costruisce l'insieme delle parti elemento per elemento. Si inizia con [[] ] (l'insieme vuoto). Per ogni nuovo elemento, si duplicano tutti i sottoinsiemi esistenti e si aggiunge il nuovo elemento a ciascun duplicato. Dopo aver elaborato n elementi, il risultato contiene tutti i 2ⁿ sottoinsiemi. È equivalente alle maschere di bit, ma più leggibile per chi non ha familiarità con le operazioni bitwise.
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]]Sottoinsiemi II: gestione dei duplicati
Quando l'input contiene duplicati, l'approccio ingenuo genera sottoinsiemi duplicati. Per [1, 2, 2], entrambe le occorrenze di 2 produrrebbero [1, 2] indipendentemente. Soluzione: ordini prima l'array, poi salti un candidato al livello corrente se è uguale al candidato precedente allo stesso livello. In particolare, nel ciclo: 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 subsetsPerché il salto dei duplicati funziona
La condizione i > start and nums[i] == nums[i-1] salta un duplicato solo allo stesso livello di ricorsione (lo stesso start). Non impedisce di selezionare lo stesso valore a profondità diverse. Per [1, 2, 2]: al livello 0 includiamo il primo 2 (indice 1), poi al livello successivo (start=2) includiamo il secondo 2 per formare [2, 2]. Ma se provassimo a includere di nuovo il secondo 2 al livello 0, la condizione lo intercetterebbe e lo salterebbe.
# 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') # 6Sottoinsiemi di dimensione fissa (k-combinazioni)
Generare solo sottoinsiemi di dimensione esattamente k (LeetCode 77: Combinations) aggiunge una condizione di terminazione anticipata: se gli elementi rimanenti non possono completare il percorso fino alla dimensione k, si pota la ricerca. La condizione che consente la potatura è i > n - (k - len(path)): se non rimangono abbastanza elementi, ci si ferma in anticipo. Questo riduce significativamente lo spazio di ricerca rispetto a generare tutti i sottoinsiemi e poi filtrarli.
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) = 120Applicazioni dell'insieme delle parti
Il modello dell'insieme delle parti ricorre in molte varianti da colloquio: (1) Partizione in due sottoinsiemi di uguale somma — verificare se un sottoinsieme ha somma pari a total/2. (2) XOR massimo di due sottoinsiemi — provare tutte le coppie di sottoinsiemi. (3) Costo minimo per scegliere k elementi — enumerare i k-sottoinsiemi. Sebbene l'enumerazione diretta sia esponenziale, molti di questi problemi ammettono soluzioni con DP una volta riconosciuta la struttura. Il modello dell'insieme delle parti aiuta a identificare lo spazio degli stati anche quando lo si ottimizza.
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)) # 20Verifica della somma di un sottoinsieme
Subset Sum chiede: esiste un sottoinsieme dell'array la cui somma sia uguale a un target? Il problema può essere risolto con il backtracking (esponenziale) o con la DP (polinomiale). La versione con backtracking è semplice, ma diventa impraticabile per input di grandi dimensioni. La versione con DP (tabella booleana dp[target+1]) è l'approccio preferito nei colloqui. Comprendere entrambi gli approcci aiuta a comunicare il compromesso: il backtracking restituisce tutte le soluzioni, mentre la DP risponde in modo efficiente al problema decisionale.
# 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)) # TrueComplessità dell'enumerazione dei sottoinsiemi
Generare tutti i sottoinsiemi ha una complessità temporale inevitabile pari a O(n × 2ⁿ): 2ⁿ sottoinsiemi, ciascuno di dimensione media n/2. Nessun algoritmo può fare meglio quando sono richiesti tutti i sottoinsiemi. Per i problemi che chiedono un singolo sottoinsieme con una determinata proprietà (come la somma massima), è preferibile usare la DP o un algoritmo greedy. Un punto chiave nei colloqui è chiedersi sempre se sia necessario enumerare tutti i sottoinsiemi oppure soltanto verificare se un qualsiasi sottoinsieme soddisfa una condizione: la risposta determina se sia accettabile un tempo esponenziale o polinomiale.
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')Confronto tra i tre approcci
Per generare tutti i sottoinsiemi: il Backtracking è l'approccio più generalizzabile, perché si adatta facilmente ai duplicati e ai vincoli. Il Bit masking è conciso e veloce, ma è limitato a n ≤ 30 (a causa della dimensione degli interi). L'approccio iterativo è intuitivo ed evita l'overhead della ricorsione. Tutti e tre producono un output di dimensione O(n × 2ⁿ). In un colloquio, il backtracking dimostra la comprensione del processo decisionale ricorsivo, che si generalizza a problemi più complessi. Quando si discutono gli approcci, è opportuno menzionarli tutti e tre.
# 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 8Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: il backtracking genera tutti i sottoinsiemi aggiungendo ogni percorso parziale ai risultati prima di esplorarlo ulteriormente, i duplicati vengono gestiti ordinando i valori e saltando quelli ripetuti allo stesso livello di ricorsione con la condizione i > start and nums[i] == nums[i-1] e il bit masking offre un'alternativa iterativa concisa, in cui ogni sottoinsieme corrisponde a una maschera di bit univoca. Ora passeremo a Permutazioni e Combinazioni, problemi di enumerazione correlati ma caratterizzati da vincoli diversi.
Domande Frequenti
La lezione «Sottoinsiemi e insieme delle parti» è gratuita?
Sì — il testo completo di «Sottoinsiemi e insieme delle parti» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sottoinsiemi e insieme delle parti»?
Generi tutti i sottoinsiemi di un insieme usando il backtracking e le maschere di bit, gestendo i duplicati ordinando gli elementi e saltando quelli ripetuti. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Sottoinsiemi e insieme delle parti»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema del backtracking: scegliere, esplorare, annullare la scelta
- Sottoinsiemi e insieme delle parti
- Permutazioni e combinazioni
- N-regine e propagazione dei vincoli