Permutações e combinações
Enumere todas as permutações de uma lista com e sem elementos duplicados e gere todas as combinações de k elementos e as variantes de soma de combinações.
Permutações e combinações é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 3 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Permutações versus combinações
Permutações são arranjos nos quais a ordem importa: [1,2,3] e [3,2,1] são diferentes. O número de permutações de n itens é n!. Combinações são seleções nas quais a ordem não importa: escolher {1,2} é o mesmo que escolher {2,1}. O número de k-combinações de n itens é C(n,k) = n! / (k! × (n-k)!). Ambos são padrões essenciais em problemas de entrevistas que envolvem contagem, enumeração e seleção.
import math
# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24
# Combinations
for k in range(n+1):
print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)Gerando todas as permutações
Use um vetor booleano used para acompanhar quais elementos estão no caminho atual. A cada etapa, tente todos os elementos não utilizados. Depois de explorá-lo, marque novamente o elemento como não utilizado. Ao contrário dos subconjuntos, não há um índice start, porque as permutações usam os elementos em qualquer ordem. A recursão termina quando len(path) == n.
def permutations(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True # CHOOSE
path.append(num)
backtrack(path) # EXPLORE
path.pop() # UNCHOOSE
used[i] = False
backtrack([])
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Permutações baseadas em troca
Uma alternativa é trocar o elemento na posição start com cada elemento entre start e n-1, fazer a recursão e, em seguida, desfazer a troca. Isso modifica o vetor diretamente, sem um vetor used. A ideia central é que, em cada nível, tudo à esquerda de start está fixo, e escolhemos qual elemento colocar na posição start. Essa abordagem é um pouco mais eficiente em termos de memória e serve de base para o algoritmo de Heap.
def permutations_swap(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # CHOOSE (swap)
backtrack(start + 1) # EXPLORE
nums[start], nums[i] = nums[i], nums[start] # UNCHOOSE (swap back)
backtrack(0)
return result
print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different orderPermutações II: tratamento de duplicatas
Quando a entrada contém duplicatas (por exemplo, [1, 1, 2]), a abordagem com o vetor used gera permutações duplicadas. Correção: ordene o vetor e ignore uma duplicata se o elemento idêntico anterior não tiver sido usado nesta chamada recursiva. A condição é: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. Isso garante que as duplicatas sejam sempre escolhidas da esquerda para a direita.
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i in range(len(nums)):
if used[i]: continue
# Skip if this num is a duplicate and the previous dup was not used
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
print(permutations_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6Próxima permutação (lexicográfica)
Próxima permutação (LeetCode 31) transforma um vetor na próxima permutação lexicograficamente maior, diretamente no próprio vetor. Algoritmo: (1) encontre o índice mais à direita i em que nums[i] < nums[i+1]. (2) Encontre o índice mais à direita j em que nums[j] > nums[i]. (3) Troque nums[i] e nums[j]. (4) Inverta o sufixo após o índice i. Se não existir tal i, inverta o vetor inteiro (voltando à menor permutação).
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost i where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost j where nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix after i
nums[i+1:] = nums[i+1:][::-1]
return nums
print(next_permutation([1, 2, 3])) # [1,3,2]
print(next_permutation([3, 2, 1])) # [1,2,3] (wraps)
print(next_permutation([1, 1, 5])) # [1,5,1]Busca com retrocesso para k-combinações
Gere todas as combinações de k elementos entre n (LeetCode 77). Use um índice inicial, como nos subconjuntos, para evitar revisitar elementos e manter a ordem crescente. Faça a poda quando restarem menos que k - len(path) elementos: if len(nums) - i + 1 < k - len(path): break. Isso equivale ao combine(n, k) apresentado anteriormente, mas operando sobre um vetor real.
def combinations(nums, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(nums)):
# Pruning: not enough elements left
if len(nums) - i < k - len(path):
break
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3)) # 10Soma de combinações: reutilização ilimitada
Soma de combinações (LeetCode 39) permite que cada número seja usado um número ilimitado de vezes. A diferença em relação às combinações padrão é que, em vez de avançar start para i+1, passamos i (o mesmo índice) para permitir a reutilização do elemento atual. Para fazer a poda: se o alvo restante se tornar 0, registre o caminho; se ficar negativo, pare. A ordenação permite o encerramento antecipado quando todos os candidatos restantes excedem o alvo restante.
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # all remaining are too big
path.append(c)
backtrack(i, path, remaining - c) # reuse allowed: pass i, not i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]Soma de combinações II: sem reutilização, com duplicatas
Soma de combinações II (LeetCode 40) usa cada número no máximo uma vez, mas a entrada pode conter duplicatas. A solução combina duas técnicas: avance start para i+1 (sem reutilização) e ignore duplicatas no mesmo nível (if i > start and nums[i] == nums[i-1]: continue) depois de ordenar. Isso une o tratamento de duplicatas de Subconjuntos II à restrição de não reutilização das combinações.
def combination_sum_ii(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
# Skip duplicates at same level
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i]) # no reuse: i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]Combinações de letras de um número de telefone
Combinações de letras (LeetCode 17) associa cada dígito às letras de um teclado de telefone e gera todas as combinações de letras possíveis para uma determinada cadeia de dígitos. Este é um problema de busca com retrocesso no qual, a cada posição, escolhemos uma letra do mapeamento do dígito e fazemos a recursão. Para uma cadeia de tamanho n com uma média de k letras por dígito, a complexidade de tempo é O(kⁿ).
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']Comparando permutações e combinações
Principais diferenças estruturais: Permutações — não usam um índice inicial, usam um vetor used ou trocas para evitar reutilização, a árvore tem n escolhas em cada nível e n! folhas ao todo. Combinações — usam um índice inicial para impor a ordenação e têm C(n,k) folhas. Soma de combinações — não avançam o índice inicial para permitir reutilização e fazem a poda com base no alvo. Mapear qualquer problema novo para uma dessas três formas fornece imediatamente o modelo correto.
# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)
# Quick reference:
import math
n = 5
print(f'Perm({n}) = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')Complexidade e dicas para entrevistas
A complexidade de tempo da enumeração é: Permutações O(n × n!), Combinações O(k × C(n,k)), Soma de combinações O(n^(T/min_val)). O espaço é O(n) para a profundidade da recursão, mais O(saída) para os resultados. Dicas importantes: (1) Esclareça sempre se a ordem importa (permutação ou combinação). (2) Mencione o tratamento de duplicatas antes que lhe perguntem. (3) Declare sempre a condição de poda explicitamente. (4) Para n grande, observe que a própria saída é exponencial — o algoritmo é ótimo para a tarefa.
import math
# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')
# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'Verificaçã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: as permutações usam um vetor de elementos usados e nenhum índice inicial, gerando n! arranjos, as combinações usam um índice inicial que avança para evitar reutilização, gerando C(n,k) seleções e as duplicatas em ambos os problemas são tratadas ordenando os valores e ignorando os valores repetidos no mesmo nível de recursão. A seguir, aplicaremos a busca com retrocesso ao problema das N-Rainhas e exploraremos a propagação de restrições.
Perguntas Frequentes
A aula “Permutações e combinações” é grátis?
Sim — o texto completo de “Permutações e combinações” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Permutações e combinações”?
Enumere todas as permutações de uma lista com e sem elementos duplicados e gere todas as combinações de k elementos e as variantes de soma de combinações. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 3 de 4.
Quanto tempo leva a aula “Permutações e combinações”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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