Permutaciones y combinaciones
Enumere todas las permutaciones de una lista, con y sin elementos duplicados, y genere todas las combinaciones de k elementos y las variantes de suma de combinaciones.
Permutaciones y combinaciones es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Permutaciones frente a combinaciones
Las permutaciones son ordenaciones en las que el orden importa: [1,2,3] y [3,2,1] son diferentes. El número de permutaciones de n elementos es n!. Las combinaciones son selecciones en las que el orden no importa: elegir {1,2} es lo mismo que elegir {2,1}. El número de k-combinaciones de n elementos es C(n,k) = n! / (k! × (n-k)!). Ambos son patrones fundamentales en problemas de entrevistas relacionados con contar, enumerar y seleccionar.
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)Generación de todas las permutaciones
Use un array booleano used para llevar el control de los elementos que están en la ruta actual. En cada paso, pruebe todos los elementos que aún no se hayan usado. Después de explorar una opción, vuelva a marcar el elemento como no utilizado. A diferencia de los subconjuntos, no hay un índice start, porque las permutaciones usan los elementos en cualquier orden. La recursión termina cuando 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]]Permutaciones basadas en intercambios
Otra alternativa consiste en intercambiar el elemento de la posición start con cada elemento desde start hasta n-1, aplicar la recursión y deshacer después el intercambio. Esto modifica el array directamente, sin un array used. La idea clave es que, en cada nivel, todo lo que queda a la izquierda de start está fijado, y se elige qué elemento colocar en la posición start. Este enfoque utiliza ligeramente menos memoria y constituye la base del 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 orderPermutaciones II: gestión de duplicados
Cuando la entrada contiene duplicados (por ejemplo, [1, 1, 2]), el enfoque del array used genera permutaciones duplicadas. La solución consiste en ordenar el array y omitir un duplicado si el elemento idéntico anterior no se utilizó en esta llamada recursiva. La condición es: if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue. Esto garantiza que los duplicados siempre se elijan de izquierda a derecha.
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 6Siguiente permutación (orden lexicográfico)
Next Permutation (LeetCode 31) transforma un array, directamente, en su siguiente permutación mayor en orden lexicográfico. Algoritmo: (1) buscar el índice más a la derecha i donde nums[i] < nums[i+1]; (2) buscar el índice más a la derecha j donde nums[j] > nums[i]; (3) intercambiar nums[i] y nums[j]; (4) invertir el sufijo posterior al índice i. Si no existe tal i, invertir el array completo (se vuelve a la permutación más pequeña).
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]Backtracking de k-combinaciones
Genere todas las combinaciones de k elementos a partir de n (LeetCode 77). Use un índice de inicio (como en los subconjuntos) para evitar volver a visitar elementos y mantener el orden. Pode cuando queden menos de k - len(path) elementos: if len(nums) - i + 1 < k - len(path): break. Esto equivale al método anterior combine(n, k), pero operando sobre un array 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)) # 10Combination Sum: reutilización ilimitada
Combination Sum (LeetCode 39) permite utilizar cada número un número ilimitado de veces. La diferencia respecto a las combinaciones estándar es que, en lugar de avanzar start hasta i+1, se pasa i (el mismo índice) para permitir reutilizar el elemento actual. Poda: si el objetivo restante llega a 0, se registra la ruta; si se vuelve negativo, se detiene la exploración. Ordenar los elementos permite terminar anticipadamente cuando todos los candidatos restantes superan el objetivo 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]]Combination Sum II: sin reutilización y con duplicados
Combination Sum II (LeetCode 40) utiliza cada número como máximo una vez, pero la entrada puede contener duplicados. Combina dos técnicas: avanzar start hasta i+1 (sin reutilización) y omitir los duplicados del mismo nivel (if i > start and nums[i] == nums[i-1]: continue) después de ordenar. Es la combinación de la gestión de duplicados de Subsets II y la restricción de no reutilización de las combinaciones.
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]]Combinaciones de letras de un número de teléfono
Letter Combinations (LeetCode 17) asigna a cada dígito las letras correspondientes de un teclado telefónico y genera todas las combinaciones posibles de letras para una cadena de dígitos determinada. Es un problema de backtracking en el que, en cada posición, se elige una letra de la asignación del dígito y se continúa con la recursión. Para una cadena de longitud n con una media de k letras por dígito, la complejidad temporal es 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']Comparación de permutaciones y combinaciones
Diferencias estructurales clave: Permutaciones — no usan un índice de inicio; utilizan un array used o intercambios para evitar la reutilización; el árbol tiene n opciones en cada nivel y un total de n! hojas. Combinaciones — utilizan un índice de inicio para imponer el orden y tienen C(n,k) hojas. Combination Sum — no avanzan el índice de inicio para permitir la reutilización y podan según el objetivo. Identificar cualquiera de los problemas nuevos con una de estas tres formas permite elegir de inmediato la plantilla adecuada.
# 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}')Complejidad y consejos para entrevistas
La complejidad temporal de la enumeración es: permutaciones O(n × n!), combinaciones O(k × C(n,k)) y Combination Sum O(n^(T/min_val)). El espacio es O(n) para la profundidad de la recursión, más O(salida) para los resultados. Consejos clave: (1) aclare siempre si el orden importa (permutación o combinación); (2) mencione la gestión de duplicados antes de que se lo pregunten; (3) indique siempre explícitamente la condición de poda; (4) para valores grandes de n, señale que la propia salida es exponencial: el algoritmo es óptimo para la tarea.
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)'Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido que: las permutaciones utilizan un array used y no tienen índice de inicio, por lo que generan n! ordenaciones, las combinaciones utilizan un índice de inicio que avanza para evitar la reutilización, por lo que generan C(n,k) selecciones, y los duplicados en ambos problemas se gestionan ordenando los valores y omitiendo los repetidos en el mismo nivel de recursión. A continuación aplicaremos el backtracking al problema de las N reinas y exploraremos la propagación de restricciones.
Aprende Python con un tutor de IA — gratis
Escribe y ejecuta código real en tu navegador, obtén ayuda instantánea de un tutor de IA disponible 24/7 y continúa donde lo dejaste en la web o en la aplicación.
- Cursos
- 30
- Lecciones
- 120
Preguntas frecuentes
¿La lección «Permutaciones y combinaciones» es gratis?
Sí — el texto completo de «Permutaciones y combinaciones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Permutaciones y combinaciones»?
Enumere todas las permutaciones de una lista, con y sin elementos duplicados, y genere todas las combinaciones de k elementos y las variantes de suma de combinaciones. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Permutaciones y combinaciones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Plantilla de backtracking: elegir, explorar y deshacer
- Subconjuntos y conjunto potencia
- Permutaciones y combinaciones
- N reinas y propagación de restricciones