Permutazioni e combinazioni
Enumera tutte le permutazioni di una lista, sia con elementi duplicati sia senza, e generi tutte le k-combinazioni e le varianti di combination sum.
Permutazioni e combinazioni è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Permutazioni e combinazioni
Le permutazioni sono disposizioni in cui l'ordine conta: [1,2,3] e [3,2,1] sono diverse. Il numero di permutazioni di n elementi è n!. Le combinazioni sono selezioni in cui l'ordine non conta: scegliere {1,2} equivale a scegliere {2,1}. Il numero di k-combinazioni di n elementi è C(n,k) = n! / (k! × (n-k)!). Entrambi sono pattern fondamentali nei problemi da colloquio che riguardano il conteggio, l'enumerazione e la selezione.
import math
# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24
# Combinations
for k in range(n+1):
print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)Generazione di tutte le permutazioni
Si utilizza un array booleano used per tenere traccia degli elementi presenti nel percorso corrente. A ogni passo si prova ogni elemento non ancora utilizzato. Dopo averlo esplorato, si contrassegna nuovamente l'elemento come non utilizzato. A differenza dei sottoinsiemi, non esiste un indice start, perché nelle permutazioni gli elementi possono essere utilizzati in qualsiasi ordine. La ricorsione termina quando len(path) == n.
def permutations(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True # CHOOSE
path.append(num)
backtrack(path) # EXPLORE
path.pop() # UNCHOOSE
used[i] = False
backtrack([])
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Permutazioni basate sugli scambi
Un'alternativa consiste nello scambiare l'elemento alla posizione start con ciascun elemento da start a n-1, chiamare ricorsivamente la funzione e poi annullare lo scambio. In questo modo si modifica l'array in-place senza un array used. L'idea chiave è che, a ogni livello, tutto ciò che si trova a sinistra di start è fissato e si sceglie quale elemento collocare nella posizione start. Questo approccio è leggermente più efficiente in termini di memoria ed è alla base dell'algoritmo di Heap.
def permutations_swap(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # CHOOSE (swap)
backtrack(start + 1) # EXPLORE
nums[start], nums[i] = nums[i], nums[start] # UNCHOOSE (swap back)
backtrack(0)
return result
print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different orderPermutazioni II: gestione dei duplicati
Quando l'input contiene duplicati (ad esempio [1, 1, 2]), l'approccio con l'array used genera permutazioni duplicate. La correzione consiste nell'ordinare l'array e poi saltare un duplicato se l'elemento identico precedente non è stato utilizzato in questa chiamata ricorsiva. La condizione è: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. In questo modo si impone che i duplicati vengano sempre scelti da sinistra verso destra.
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i in range(len(nums)):
if used[i]: continue
# Skip if this num is a duplicate and the previous dup was not used
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
print(permutations_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6Permutazione successiva (ordine lessicografico)
Next Permutation (LeetCode 31) trasforma un array nella permutazione successiva, maggiore in ordine lessicografico, direttamente nell'array. Algoritmo: (1) trovare l'indice più a destra i per cui nums[i] < nums[i+1]. (2) Trovare l'indice più a destra j per cui nums[j] > nums[i]. (3) Scambiare nums[i] e nums[j]. (4) Invertire il suffisso dopo l'indice i. Se non esiste un indice i di questo tipo, si inverte l'intero array, tornando alla permutazione più piccola.
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost i where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost j where nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix after i
nums[i+1:] = nums[i+1:][::-1]
return nums
print(next_permutation([1, 2, 3])) # [1,3,2]
print(next_permutation([3, 2, 1])) # [1,2,3] (wraps)
print(next_permutation([1, 1, 5])) # [1,5,1]Backtracking delle k-combinazioni
Si generano tutte le combinazioni di k elementi scelti tra n (LeetCode 77). Si utilizza un indice di partenza, come nei sottoinsiemi, per evitare di visitare nuovamente gli elementi e mantenere l'ordine ordinato. Si applica la potatura quando rimangono meno di k - len(path) elementi: if len(nums) - i + 1 < k - len(path): break. È l'equivalente del precedente combine(n, k), ma operando su un array reale.
def combinations(nums, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(nums)):
# Pruning: not enough elements left
if len(nums) - i < k - len(path):
break
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3)) # 10Combination Sum: riutilizzo illimitato
Combination Sum (LeetCode 39) consente di utilizzare ogni numero un numero illimitato di volte. La differenza rispetto alle combinazioni standard è che, invece di portare start a i+1, si passa i (lo stesso indice) per consentire il riutilizzo dell'elemento corrente. Per la potatura: se il target rimanente diventa 0, si registra il percorso; se diventa negativo, ci si ferma. L'ordinamento consente di terminare in anticipo quando tutti i candidati rimanenti superano il target residuo.
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # all remaining are too big
path.append(c)
backtrack(i, path, remaining - c) # reuse allowed: pass i, not i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]Combination Sum II: nessun riutilizzo, con duplicati
Combination Sum II (LeetCode 40) utilizza ogni numero al massimo una volta, ma l'input può contenere duplicati. Si combinano due tecniche: portare start a i+1 (nessun riutilizzo) e saltare i duplicati allo stesso livello (if i > start and nums[i] == nums[i-1]: continue) dopo aver ordinato l'array. Si tratta dell'unione della gestione dei duplicati usata in Subsets II e del vincolo di non riutilizzo delle combinazioni.
def combination_sum_ii(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
# Skip duplicates at same level
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i]) # no reuse: i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]Combinazioni di lettere di un numero di telefono
Letter Combinations (LeetCode 17) associa ogni cifra alle lettere corrispondenti sulla tastiera di un telefono e genera tutte le possibili combinazioni di lettere per una determinata stringa di cifre. Si tratta di un problema di backtracking in cui, a ogni posizione, si sceglie una lettera dalla corrispondenza della cifra e si procede ricorsivamente. Per una stringa di lunghezza n con una media di k lettere per cifra, la complessità temporale è O(kⁿ).
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']Confronto tra permutazioni e combinazioni
Differenze strutturali fondamentali: le permutazioni — nessun indice di partenza, si utilizza un array used oppure lo scambio per evitare il riutilizzo; l'albero ha n scelte a ogni livello e n! foglie in totale. Le combinazioni — si utilizza un indice di partenza per imporre l'ordine e si ottengono C(n,k) foglie. Combination Sum — non si fa avanzare l'indice di partenza per consentire il riutilizzo e si applica la potatura sul target. Ricondurre un nuovo problema a una di queste tre forme consente di scegliere immediatamente il template corretto.
# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)
# Quick reference:
import math
n = 5
print(f'Perm({n}) = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')Complessità e consigli per i colloqui
La complessità temporale dell'enumerazione è: permutazioni O(n × n!), combinazioni O(k × C(n,k)), Combination Sum O(n^(T/min_val)). Lo spazio è O(n) per la profondità della ricorsione, più O(output) per i risultati. Consigli fondamentali: (1) chiarisca sempre se l'ordine conta (permutazione o combinazione). (2) Menzioni la gestione dei duplicati prima che Le venga chiesto. (3) Espliciti sempre la condizione di potatura. (4) Per n grandi, osservi che anche l'output è esponenziale: l'algoritmo è ottimale per il compito.
import math
# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')
# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'Verifica 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: le permutazioni utilizzano un array used e nessun indice start, generando n! disposizioni, le combinazioni utilizzano un indice start che avanza per evitare il riutilizzo, generando C(n,k) selezioni e i duplicati in entrambi i problemi vengono gestiti ordinando i valori e saltando quelli ripetuti allo stesso livello di ricorsione. Ora applicheremo il backtracking al problema delle N-Queens ed esploreremo la propagazione dei vincoli.
Domande Frequenti
La lezione «Permutazioni e combinazioni» è gratuita?
Sì — il testo completo di «Permutazioni e combinazioni» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Permutazioni e combinazioni»?
Enumera tutte le permutazioni di una lista, sia con elementi duplicati sia senza, e generi tutte le k-combinazioni e le varianti di combination sum. Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 3 di 4.
Quanto tempo richiede la lezione «Permutazioni e combinazioni»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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