Gere Todos os Subconjuntos
Escolha ou ignore cada elemento.
Gere Todos os Subconjuntos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Por que gerar subconjuntos
Muitas tarefas de competição pedem que você tente cada subconjunto de um conjunto pequeno. Com recursão, você pode listar todos eles de forma clara e confiável. 🧩
Escolha ou ignore cada elemento
A ideia central é: para cada elemento, faça uma escolha binária, incluindo-o ou deixando-o de fora. Cada conjunto completo de escolhas produz um subconjunto.
Quantos subconjuntos existem
Um conjunto com n elementos tem exatamente 2 elevado a n subconjuntos, porque cada elemento dobra a quantidade. Portanto, mantenha n pequeno, em torno de 20 ou menos.
O plano recursivo
Percorra o vetor usando um índice. Em cada índice, crie dois ramos: em um, escolha o elemento; no outro, ignore-o.
O caso-base
Quando o índice ultrapassa o último elemento, o caminho atual é um subconjunto completo. Esse é o seu caso-base para registrá-lo.
Recursão de subconjuntos no código
Esta varredura recursiva registra um subconjunto no final e depois explora as opções de ignorar e escolher em cada índice.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Faça retrocesso desfazendo a escolha
Quando você usa append para adicionar um elemento, remova-o depois da recursão para que o próximo ramo comece limpo. Essa etapa de desfazer é o coração do retrocesso.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()A alternativa da máscara de bits
Você também pode associar cada inteiro de 0 a 2 elevado a n menos 1 a um subconjunto, em que cada bit indica um elemento incluído.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Copie antes de armazenar
Sempre armazene uma cópia da lista atual, não a própria lista. Caso contrário, alterações posteriores substituirão todos os subconjuntos salvos. ⚠️
Gerando combinações
Para obter subconjuntos de tamanho fixo k, pare o ramo quando a contagem de elementos escolhidos chegar a k. Isso transforma subconjuntos em combinations.
Onde os subconjuntos aparecem
A enumeração de subconjuntos resolve pequenos problemas de mochila, seleção de equipes e verificações de viabilidade em que você precisa testar todas as seleções possíveis.
Verificação rápida
Quantos subconjuntos tem um conjunto com n elementos?
Recapitulação: ramifique em cada elemento
Você aprendeu a listar todos os subconjuntos escolhendo ou ignorando cada elemento e desfazendo a escolha após cada ramo. Mantenha n pequeno, pois a quantidade é 2 elevado a n. 🎯
Perguntas Frequentes
A aula “Gere Todos os Subconjuntos” é grátis?
Sim — o texto completo de “Gere Todos os Subconjuntos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Gere Todos os Subconjuntos”?
Escolha ou ignore cada elemento. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Gere Todos os Subconjuntos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pense Recursivamente: Base e Recursão
- Gere Todos os Subconjuntos
- Permutações e a Ideia das N-Rainhas
- Faça Poda para Sobreviver ao Limite de Tempo