Subsets

+10

Você recebe uma lista nums de números inteiros distintos. Retorne todos os seus subconjuntos, incluindo o vazio e a lista completa; assim, n valores geram 2^n subconjuntos. Escreva cada subconjunto com seus valores em ordem crescente e liste os subconjuntos em ordem lexicográfica: compare os valores dos dois subconjuntos um a um; a primeira diferença decide, e um subconjunto que é o início de outro vem antes dele. Para [1, 2], a resposta é [[], [1], [1, 2], [2]].

Função

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

numsinteger-array: os valores, todos diferentes, em qualquer ordem
Retornainteger-2d-array: todos os subconjuntos, cada um ordenado em ordem crescente, listados em ordem lexicográfica

Restrições

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
Todos os valores em nums são diferentes.
nums pode vir em qualquer ordem.

Exemplos

Entrada: nums = [3, 1, 2]
Saída: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Explicação: Em ordem crescente, os valores são 1, 2, 3, e três valores geram 2^3 = 8 subconjuntos. [1, 2] vem antes de [1, 2, 3] porque é seu início, e [1, 2, 3] vem antes de [1, 3] porque 2 é menor que 3 na segunda posição.

Entrada: nums = [0]
Saída: [[], [0]]
Explicação: Um valor tem dois subconjuntos: deixe-o de fora e obtenha [], ou inclua-o e obtenha [0]. O subconjunto vazio sempre vem primeiro.

Entrada: nums = [5, -2]
Saída: [[], [-2], [-2, 5], [5]]
Explicação: Os valores são ordenados como -2 e 5, então [-2, 5] é escrito nessa ordem. Todo subconjunto que contém -2 vem antes de [5], porque -2 é menor que 5.

+13 testes ocultos ao enviar

Para ir além

Você consegue produzir a mesma lista sem recursão, construindo cada subconjunto diretamente a partir do anterior?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Há 2^n subconjuntos, então nenhum método faz menos que O(2^n) trabalho. A questão real é como produzir cada subconjunto uma única vez, na ordem exigida, sem ordenar 1024 listas depois. Fazer backtracking sobre os valores ordenados, registrando cada nó da árvore de decisão ao entrar nele, percorre os subconjuntos exatamente em ordem lexicográfica.

Máscaras de bits, depois ordene

Intuição

Alinhe os valores ordenados nas posições de 0 a n-1. Um subconjunto indica sim ou não para cada posição, e é isso que os n bits de um número fazem. Portanto, os números de 0 a 2^n-1 são os subconjuntos: para [1, 2, 3], a máscara 5 é 101 em binário, os bits 0 e 2 estão definidos, e ela representa [1, 3]. A máscara 0 é o subconjunto vazio e a máscara 7 é a lista completa.

Máscaras diferentes geram subconjuntos diferentes, e todo subconjunto tem uma máscara, então o loop produz todos os 2^n subconjuntos exatamente uma vez. Ler os bits da posição 0 para cima nos valores ordenados escreve cada subconjunto em ordem crescente.

As máscaras não aparecem na ordem pedida pelo problema. A máscara 1 é [1], a máscara 2 é [2] e a máscara 3 é [1, 2], então [2] ficaria antes de [1, 2]. Você corrige isso com uma ordenação cujo comparador compara valor por valor e coloca um prefixo primeiro. A ordenação custa mais do que a geração: 2^n subconjuntos precisam de cerca de n × 2^n comparações, e cada comparação lê até n valores. Para n = 10, isso dá cerca de 10^5 leituras, ainda rápido, mas é um trabalho que a próxima abordagem nunca faz.

Algoritmo

Ordene nums para que cada subconjunto seja lido em ordem crescente.
Para cada máscara de 0 a 2^n-1, reúna os valores nas posições cujo bit está definido.
Ordene a lista de subconjuntos: na primeira posição em que dois diferem, o menor valor vem primeiro e, se um deles acabar antes, ele vem primeiro.
Retorne a lista ordenada.

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: escolha, explore, desfaça a escolha

Intuição

Imagine os subconjuntos como uma árvore. A raiz é o subconjunto vazio. Abaixo de um nó, você pode adicionar qualquer valor que seja maior que o último que adicionou. Para os valores ordenados [1, 2, 3], a raiz tem os filhos [1], [2] e [3]; [1] tem os filhos [1, 2] e [1, 3]; [1, 2] tem o filho [1, 2, 3]. Cada subconjunto aparece exatamente uma vez nessa árvore, porque só há uma maneira de escrevê-lo em ordem crescente, e cada nó é uma resposta, não apenas as folhas.

O retrocesso percorre a árvore com uma única lista compartilhada, path. Para descer até um filho, você escolhe: adiciona o valor. Você explora: faz uma chamada recursiva, e a função auxiliar registra uma cópia de path assim que chega ao nó. Então você desfaz a escolha: remove o valor, para que path volte ao nó pai e seja possível testar o próximo irmão. Como cada nó é registrado ao chegar a ele, um nó pai sempre é escrito antes de seus filhos.

É por isso que a saída fica em ordem lexicográfica sem precisar ordenar. Os filhos de um nó são testados do menor valor para o maior, e o percurso termina um ramo inteiro antes de iniciar o próximo. Para [1, 2, 3], ele registra [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: a ordem de um dicionário, com um prefixo antes de suas extensões.

A árvore tem 2^n nós e copiar um caminho custa até n, então o tempo é O(n × 2^n), o tamanho da própria resposta. Além da saída, você mantém um caminho e uma pilha de chamadas, ambos com profundidade máxima n.

Algoritmo

Ordene os valores.
Escreva explore(start). Primeiro, ele adiciona uma cópia de path ao resultado.
Em seguida, para cada índice i de start até o final: adicione values[i] a path (escolha), chame explore(i+1) (explore) e remova o último valor (desfaça a escolha).
Chame explore(0) com um caminho vazio e retorne o resultado.

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

Armadilhas e casos extremos

A maioria das respostas erradas aqui se deve à ordem ou ao compartilhamento de uma lista.

Adicionar o próprio path em vez de uma cópia. Todas as entradas então apontam para a mesma lista, que estará vazia quando a busca terminar; assim, você retorna 2^n cópias de [].
Esquecer de ordenar nums. Com [3, 1, 2], a árvore constrói [3, 1], que não está em ordem crescente, e a busca deixa de estar em ordem lexicográfica.
Registrar apenas nas folhas, como você faria para permutações. Cada nó desta árvore é um subconjunto; registrar apenas os caminhos que chegam ao fim retorna poucos subconjuntos.
Fazer a recursão com start+1 em vez de i+1. Assim, um valor pode vir depois de um maior ou até dele mesmo, e você obtém listas como [3, 2] e [3, 3], que não são subconjuntos em ordem crescente.
Usar a árvore de inclusão ou exclusão (decidir o valor 0, depois o valor 1 e assim por diante) e registrar as folhas. Ela encontra todos os 2^n subconjuntos, mas tentar incluir primeiro coloca a lista completa em primeiro lugar, e tentar excluir primeiro coloca [3] antes de [2]. Nenhuma das opções está em ordem lexicográfica.
Um comparador que ordena primeiro pelo comprimento resulta em [], [1], [2], [3], [1, 2], que é uma ordem diferente.

Perguntas frequentes4

Quantos subconjuntos tem um conjunto de n elementos?

2^n. Cada elemento está dentro ou fora, independentemente dos outros, então as escolhas se multiplicam: duas para o primeiro elemento, duas para o segundo e assim por diante. Três valores geram 8 subconjuntos e dez geram 1024, contando o subconjunto vazio e o conjunto completo.

Qual é a complexidade de tempo do problema dos subconjuntos?

O(n × 2^n). Há 2^n subconjuntos, e escrever cada um deles leva até n etapas, então até mesmo retornar a resposta custa esse tanto. A retrocessão atinge esse limite e usa apenas O(n) de espaço extra. Gerar com máscaras de bits é tão rápido quanto, mas ordenar o resultado depois adiciona outro fator de n.

Devo usar retrocesso ou máscaras de bits para subconjuntos?

Máscaras de bits são curtas, não precisam de recursão e tornam visível a escolha de incluir ou não incluir como bits. O backtracking gera os subconjuntos em ordem lexicográfica por si só e se adapta às variantes comuns: ignorar valores repetidos, considerar apenas subconjuntos de tamanho k ou apenas subconjuntos que atinjam uma soma-alvo, caso em que você pode parar de explorar um ramo antecipadamente.

Como você lida com valores duplicados em Subsets?

Ordene os valores e, em seguida, no loop da função auxiliar de retrocesso, ignore um valor que seja igual ao anterior no mesmo nível: i > start e values[i] == values[i-1]. A primeira cópia já explora todos os subconjuntos que a utilizam, então um ramo irmão que começa com a segunda cópia apenas reconstruiria os mesmos subconjuntos.

Python

def subsets(nums):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [3, 1, 2]

Esperado

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