Subconjuntos e conjunto das partes
Gere todos os subconjuntos de um conjunto usando retrocesso e máscaras de bits, tratando duplicatas ao ordenar e ignorar elementos repetidos.
Subconjuntos e conjunto das partes é 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.
Subconjuntos e o conjunto das partes
O conjunto das partes de um conjunto S é a coleção de todos os subconjuntos possíveis de S, incluindo o conjunto vazio e o próprio S. Um conjunto com n elementos tem exatamente 2ⁿ subconjuntos. Para [1, 2, 3], os 8 subconjuntos são: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Este é um problema combinatório fundamental, presente em perguntas de entrevistas sobre encontrar todas as combinações, partições ou escolhas possíveis.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Geração de subconjuntos com retrocesso
Use o modelo escolher-explorar-desfazer. A principal decisão de projeto é: em cada chamada recursiva, adicione o caminho parcial atual aos resultados imediatamente (antes de escolher mais elementos). Dessa forma, cada estado — vazio, parcial e completo — é capturado como um subconjunto válido. Avance o índice start para considerar apenas os elementos à direita do último elemento escolhido, garantindo que não haja duplicatas e preservando a ordem.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Abordagem com máscaras de bits
Uma alternativa ao retrocesso é a máscara de bits: cada subconjunto corresponde a um número de n bits, no qual o bit i igual a 1 significa que o elemento i está incluído. Percorra de 0 até 2ⁿ - 1 e, para cada número, extraia os bits para construir o subconjunto. Essa abordagem é iterativa, costuma ser mais rápida na prática e é muito fácil de programar. No entanto, ela não se generaliza tão bem para problemas com restrições (como um limite de soma).
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differGeração iterativa de subconjuntos
A abordagem iterativa constrói o conjunto das partes elemento por elemento. Comece com [[] ] (o conjunto vazio). Para cada novo elemento, duplique todos os subconjuntos existentes e anexe o novo elemento a cada duplicata. Depois de processar n elementos, o resultado contém todos os 2ⁿ subconjuntos. Isso equivale às máscaras de bits, mas é mais legível para quem não conhece operações bit a bit.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subconjuntos II: tratando duplicatas
Quando a entrada contém duplicatas, a abordagem ingênua gera subconjuntos duplicados. Para [1, 2, 2], as duas ocorrências de 2 produziriam [1, 2] de forma independente. Para corrigir isso, ordene o vetor primeiro e ignore uma candidata no nível atual se ela for igual à candidata anterior no mesmo nível. Especificamente, no laço: if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsPor que ignorar duplicatas funciona
A condição i > start and nums[i] == nums[i-1] ignora uma duplicata apenas no mesmo nível de recursão (mesmo start). Ela não impede a seleção do mesmo valor em profundidades diferentes. Para [1, 2, 2]: no nível 0, incluímos o primeiro 2 (índice 1) e, no nível seguinte (start=2), incluímos o segundo 2 para formar [2, 2]. Porém, se tentássemos incluir novamente o segundo 2 no nível 0, a condição o detectaria e o ignoraria.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Subconjuntos de tamanho fixo (k-combinações)
Gerar apenas subconjuntos de tamanho exatamente k (LeetCode 77: Combinações) adiciona uma condição de encerramento antecipado: se os elementos restantes não puderem completar o caminho até o tamanho k, faça a poda. A condição que permite a poda é i > n - (k - len(path)): se não houver elementos suficientes restantes, pare antecipadamente. Isso reduz significativamente o espaço de busca em comparação com gerar todos os subconjuntos e filtrá-los.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Aplicações do conjunto das partes
O padrão do conjunto das partes aparece em muitas variações de entrevistas: (1) Partição em dois subconjuntos iguais — verifique se algum subconjunto soma total/2. (2) XOR máximo de dois subconjuntos — tente todos os pares de subconjuntos. (3) Custo mínimo para escolher k itens — enumere k-subconjuntos. Embora a enumeração direta seja exponencial, muitos desses problemas admitem soluções com DP assim que você reconhece a estrutura. A formulação como conjunto das partes ajuda a identificar o espaço de estados mesmo quando você o otimiza.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Verificação da soma de subconjuntos
Soma de subconjuntos pergunta: algum subconjunto do vetor soma um determinado alvo? Isso pode ser resolvido por busca com retrocesso (exponencial) ou DP (polinomial). A versão com retrocesso é simples, mas se torna impraticável para entradas grandes. A versão com DP (tabela booleana dp[target+1]) é a abordagem preferida em entrevistas. Compreender ambas ajuda você a explicar o compromisso: o retrocesso fornece todas as soluções, enquanto DP responde ao problema de decisão com eficiência.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueComplexidade da enumeração de subconjuntos
Gerar todos os subconjuntos tem complexidade de tempo inevitável O(n × 2ⁿ) — são 2ⁿ subconjuntos, cada um com tamanho médio n/2. Nenhum algoritmo pode fazer melhor quando todos os subconjuntos são solicitados. Para problemas que pedem um único subconjunto com uma propriedade (como soma máxima), deve-se preferir DP ou uma abordagem gulosa. Percepção importante para entrevistas: pergunte sempre se é necessário enumerar todos os subconjuntos ou apenas descobrir se algum subconjunto satisfaz uma condição — a resposta determina se um tempo exponencial ou polinomial é aceitável.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Comparação das três abordagens
Para gerar todos os subconjuntos: Busca com retrocesso é a abordagem mais generalizável — adapta-se facilmente a duplicatas e restrições. Máscara de bits é concisa e rápida, mas limitada a n ≤ 30 (tamanho do inteiro). A abordagem iterativa é intuitiva e evita o custo adicional da recursão. As três produzem uma saída O(n × 2ⁿ). Em uma entrevista, a busca com retrocesso demonstra compreensão do processo recursivo de decisão, que se generaliza para problemas mais difíceis. Mencione as três ao discutir as abordagens.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a busca com retrocesso gera todos os subconjuntos adicionando cada caminho parcial aos resultados antes de continuar a exploração, as duplicatas são tratadas ordenando os valores e ignorando os valores repetidos no mesmo nível de recursão com a condição i > start e nums[i] == nums[i-1] e a máscara de bits fornece uma alternativa iterativa concisa, na qual cada subconjunto corresponde a uma máscara de bits única. A seguir, abordaremos Permutações e Combinações — problemas relacionados de enumeração com restrições diferentes.
Perguntas Frequentes
A aula “Subconjuntos e conjunto das partes” é grátis?
Sim — o texto completo de “Subconjuntos e conjunto das partes” é 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 “Subconjuntos e conjunto das partes”?
Gere todos os subconjuntos de um conjunto usando retrocesso e máscaras de bits, tratando duplicatas ao ordenar e ignorar elementos repetidos. 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 “Subconjuntos e conjunto das partes”?
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
- Modelo de Retrocesso: Escolher, Explorar, Desfazer
- Subconjuntos e conjunto das partes
- Permutações e combinações
- N-rainhas e propagação de restrições