Pular para o conteúdo

Subconjuntos

Aula 2 de 5 · 5 min

Subconjuntos

Passo 1 de 7

Um subconjunto é uma resposta de sim ou não por item, então cada nível da árvore tem exatamente dois ramos.

A ideia

Um subconjunto é uma resposta sim-ou-não por item, então a árvore de decisão é binária: pule nums[i], ou pegue-o e siga em frente.

O índice só anda para a frente, e é isso que impede que {1, 2} e {2, 1} apareçam os dois. Cada folha é um conjunto completo de decisões, então existem exatamente 2 elevado a n delas — e o pop depois do ramo de pegar é, de novo, o que mantém o caminho compartilhado íntegro.

Exemplo do mundo real

Escolher quais módulos opcionais ativar num build. Cada flag é independente, e o time de release quer todas as combinações testadas — oito builds para três flags, dezesseis para quatro.

O código

Sua vez

O que isto imprime?

out = []
subsets([1, 2, 3], 0, [], out)
print(len(out))

Mini quiz

1 / 3

Quantas folhas a árvore de subconjuntos tem para n itens?