Subsets

+10

Ricevi una lista nums di numeri interi distinti. Restituisci tutti i suoi sottoinsiemi, incluso quello vuoto e la lista completa, quindi n valori danno 2^n sottoinsiemi. Scrivi ogni sottoinsieme con i suoi valori in ordine crescente e disponi i sottoinsiemi in ordine lessicografico: confronta i sottoinsiemi valore per valore; decide la prima differenza e, se un sottoinsieme è l'inizio di un altro, viene prima. Per [1, 2] la risposta è [[], [1], [1, 2], [2]].

Funzione

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

numsinteger-array: i valori, tutti diversi, in qualsiasi ordine
Restituisceinteger-2d-array: ogni sottoinsieme, ciascuno ordinato in ordine crescente, elencato in ordine lessicografico

Vincoli

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Tutti i valori in nums sono diversi.
nums può essere in qualsiasi ordine.

Esempi

Input: nums = [3, 1, 2]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Spiegazione: In ordine, i valori sono 1, 2, 3, e tre valori danno 2^3 = 8 sottoinsiemi. [1, 2] viene prima di [1, 2, 3] perché ne è l’inizio, e [1, 2, 3] viene prima di [1, 3] perché 2 è minore di 3 nella seconda posizione.

Input: nums = [0]
Output: [[], [0]]
Spiegazione: Un valore ha due sottoinsiemi: escludilo e ottieni [], oppure includilo e ottieni [0]. Il sottoinsieme vuoto viene sempre per primo.

Input: nums = [5, -2]
Output: [[], [-2], [-2, 5], [5]]
Spiegazione: I valori si ordinano in -2 e 5, quindi [-2, 5] viene scritto in quest'ordine. Ogni sottoinsieme che contiene -2 viene prima di [5], perché -2 è minore di 5.

+13 test nascosti all’invio

Per approfondire

Riesci a produrre lo stesso elenco senza ricorsione, costruendo ogni sottoinsieme direttamente da quello precedente?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Ci sono 2^n sottoinsiemi, quindi nessun metodo richiede meno di O(2^n) operazioni. La vera domanda è come generare ogni sottoinsieme una sola volta, nell’ordine richiesto, senza ordinare successivamente 1024 liste. Il backtracking sui valori ordinati, registrando ogni nodo dell’albero decisionale man mano che lo si visita, attraversa i sottoinsiemi esattamente in ordine lessicografico.

Maschere di bit, poi ordina

Intuizione

Disponi i valori ordinati nelle posizioni da 0 a n-1. Un sottoinsieme indica sì o no per ogni posizione, ed è proprio ciò che fanno gli n bit di un numero. Quindi i numeri da 0 a 2^n-1 rappresentano i sottoinsiemi: per [1, 2, 3], la maschera 5 è 101 in binario, i bit 0 e 2 sono impostati e rappresenta [1, 3]. La maschera 0 è il sottoinsieme vuoto e la maschera 7 è la lista completa.

Maschere diverse danno sottoinsiemi diversi e ogni sottoinsieme ha una maschera, quindi il ciclo produce tutti i 2^n sottoinsiemi esattamente una volta. Leggere i bit partendo dalla posizione 0 e procedendo verso l’alto sui valori ordinati scrive ogni sottoinsieme in ordine crescente.

Le maschere non vengono generate nell’ordine richiesto dal problema. La maschera 1 è [1], la maschera 2 è [2] e la maschera 3 è [1, 2], quindi [2] finirebbe prima di [1, 2]. Puoi risolvere il problema con un ordinamento il cui comparatore confronta i valori uno per uno e mette prima un prefisso. L’ordinamento costa più della generazione: per 2^n sottoinsiemi servono circa n × 2^n confronti e ogni confronto legge fino a n valori. Per n = 10 si tratta di circa 10^5 letture: è comunque veloce, ma è un lavoro che l’approccio successivo non esegue mai.

Algoritmo

Ordina nums in modo che ogni sottoinsieme sia in ordine crescente.
Per ogni maschera da 0 a 2^n-1, raccogli i valori nelle posizioni il cui bit è impostato.
Ordina l'elenco dei sottoinsiemi: alla prima posizione in cui due sottoinsiemi differiscono, prevale il valore più piccolo; se uno termina prima, viene prima.
Restituisci l'elenco ordinato.

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

Backtracking: scegli, esplora, annulla la scelta

Intuizione

Immagina i sottoinsiemi come un albero. La radice è il sottoinsieme vuoto. Sotto un nodo puoi aggiungere qualsiasi valore maggiore dell’ultimo che hai aggiunto. Per i valori ordinati [1, 2, 3], la radice ha i figli [1], [2] e [3]; [1] ha i figli [1, 2] e [1, 3]; [1, 2] ha il figlio [1, 2, 3]. Ogni sottoinsieme compare in questo albero esattamente una volta, perché c’è un solo modo di scriverlo in ordine crescente, e ogni nodo è una risposta, non solo le foglie.

Il backtracking percorre l’albero con un’unica lista condivisa, path. Per scendere a un figlio, scegli: aggiungi il valore. Poi esplori: esegui la chiamata ricorsiva e la funzione ausiliaria registra una copia di path nel momento in cui arriva. Infine annulli la scelta: rimuovi il valore, così path torna al nodo genitore e si può provare il fratello successivo. Poiché ogni nodo viene registrato appena lo si raggiunge, un genitore viene sempre scritto prima dei suoi figli.

Ecco perché l’output è in ordine lessicografico senza bisogno di ordinare. I figli di un nodo vengono provati dal valore più piccolo al più grande e il percorso completa un intero ramo prima di iniziare il successivo. Per [1, 2, 3] registra [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: l’ordine di un dizionario, con un prefisso prima delle sue estensioni.

L’albero ha 2^n nodi e copiare un percorso costa fino a n, quindi il tempo è O(n × 2^n), pari alla dimensione della risposta stessa. Oltre all’output, si mantengono un percorso e uno stack di chiamate, entrambi profondi al massimo n.

Algoritmo

Ordina i valori.
Scrivi explore(start). Per prima cosa aggiunge una copia di path al risultato.
Poi, per ogni indice i da start fino alla fine: aggiungi values[i] a path (scegli), chiama explore(i+1) (esplora) e rimuovi l'ultimo valore (annulla la scelta).
Chiama explore(0) con un percorso vuoto e restituisci il risultato.

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

Trappole e casi limite

La maggior parte delle risposte sbagliate qui dipende dall’ordine o dalla condivisione di un’unica lista.

Aggiungere path stesso invece di una copia. Ogni voce punta quindi alla stessa lista, che è vuota quando la visita termina, perciò restituisci 2^n copie di [].
Dimenticare di ordinare nums. Con [3, 1, 2] l’albero costruisce [3, 1], che non è in ordine crescente, e la visita non segue più l’ordine lessicografico.
Registrare solo nelle foglie, come faresti per le permutazioni. Ogni nodo di questo albero è un sottoinsieme; registrare solo i percorsi che arrivano alla fine restituisce troppo pochi sottoinsiemi.
Ricorrere su start+1 invece che su i+1. Un valore può quindi seguire uno più grande o persino sé stesso, e ottieni liste come [3, 2] e [3, 3], che non sono sottoinsiemi in ordine crescente.
Usare l’albero di inclusione o esclusione (decidere il valore 0, poi il valore 1 e così via) e registrare le foglie. Trova tutti i 2^n sottoinsiemi, ma provare prima l’inclusione mette per prima la lista completa, mentre provare prima l’esclusione mette [3] prima di [2]. Nessuno dei due ordini è lessicografico.
Un comparatore che ordina prima per lunghezza produce [], [1], [2], [3], [1, 2], che è un ordine diverso.

Domande frequenti4

Quanti sottoinsiemi ha un insieme di n elementi?

2^n. Ogni elemento è incluso oppure escluso, indipendentemente dagli altri, quindi le possibilità si moltiplicano: due per il primo elemento, due per il secondo e così via. Tre valori danno 8 sottoinsiemi e dieci ne danno 1024, contando il sottoinsieme vuoto e l'insieme completo.

Qual è la complessità temporale del problema dei sottoinsiemi?

O(n × 2^n). Ci sono 2^n sottoinsiemi e scriverne uno richiede fino a n passaggi, quindi anche solo restituire la risposta costa altrettanto. Il backtracking raggiunge questo limite e usa solo O(n) spazio aggiuntivo. Generarli con le maschere di bit è altrettanto veloce, ma ordinare il risultato in seguito aggiunge un altro fattore n.

Dovrei usare il backtracking o le maschere di bit per i sottoinsiemi?

Le maschere di bit sono brevi, non richiedono ricorsione e rendono visibile la scelta di includere o escludere come bit. Il backtracking genera da sé i sottoinsiemi in ordine lessicografico e si adatta alle varianti più comuni: ignorare i valori ripetuti, considerare solo i sottoinsiemi di dimensione k oppure solo quelli che raggiungono una somma obiettivo, così puoi interrompere prima l'esplorazione di un ramo.

Come si gestiscono i valori duplicati in Subsets?

Ordina i valori, poi nel ciclo della funzione ausiliaria di backtracking salta un valore uguale a quello precedente allo stesso livello: i > start e values[i] == values[i-1]. La prima copia esplora già tutti i sottoinsiemi che la includono, quindi un ramo fratello che inizia con la seconda copia ricostruirebbe solo gli stessi sottoinsiemi.

Python

def subsets(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 1, 2]

Atteso

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