Combinaciones y Permutaciones con Backtracking

Curso de Algoritmos Avanzados: Grafos y Árboles

Contenido del curso

Introducción

DFS

BFS

Backtrack

Próximos pasos

Tomar examen

Ejercicios resultado de Backtrack

Combinación de Sumas Dada una matriz de enteros distintos candidatos y un entero objetivo, devuelve una lista de todas las combinaciones únicas de candidatos en las que los números elegidos suman el objetivo. Puede devolver las combinaciones en cualquier orden. El mismo número puede ser elegido entre los candidatos un número ilimitado de veces. Dos combinaciones son únicas si la frecuencia de al menos uno de los números elegidos es diferente. Los casos de prueba se generan de forma que el número de combinaciones únicas que suman el objetivo sea inferior a 150 combinaciones para la entrada dada.

Ejemplo 1: Entrada: candidatos = [2,3,6,7], objetivo = 7 Salida: [[2,2,3],[7]] Explicación: 2 y 3 son candidatos, y 2 + 2 + 3 = 7. Nótese que 2 puede usarse varias veces. 7 es un candidato, y 7 = 7. Estas son las dos únicas combinaciones.

def combinationSum(self, candidatos: List[int], target: int) -> List[List[int]]:
   def dfs(sobrante, pila, resultado):
       if not sobrante:
           resultado.append(pila)
           return
       for numero in candidatos:
           if numero > sobrante:
               return
           if not pila or pila[-1] <= numero:
               dfs(sobrante - numero, pila + [numero], resultado)
   resultado = []
   candidatos.sort()
   dfs(target, [], resultado)
   return resultado

Permutaciones Dado un array nums de enteros distintos, devuelve todas las permutaciones posibles. Puede devolver la respuesta en cualquier orden.

Ejemplo 1: Entrada: nums = [1,2,3] Salida: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Ejemplo 2: Entrada: nums = [0,1] Salida: [[0,1],[1,0]]

def permute(self, numeros):
   def dfs(listaNumeros, combinaciónActual, permutaciones):
       if not listaNumeros:
           permutaciones.append(combinaciónActual)
       for i in range(len(listaNumeros)):
           dfs(listaNumeros[:i]+listaNumeros[i+1:], combinaciónActual+[listaNumeros[i]], permutaciones)
   permutaciones = []
   dfs(numeros, [], permutaciones)
   return permutaciones

Permutaciones Dado un array nums de enteros distintos, devuelve todas las permutaciones posibles. Puede devolver la respuesta en cualquier orden.

def letterCasePermutation(self, S: str) -> List[str]:
   res = []
   def dfs(permutacionActual, apuntador):
       if apuntador == len(S):
           res.append(''.join(permutacionActual))
           return
       for i in set([S[apuntador].lower(), S[apuntador].upper()]):
           permutacionActual.append(i)
           dfs(permutacionActual, apuntador+1)
           permutacionActual.pop()
   dfs([],0)
   return res

Combinaciones y Permutaciones con Backtracking

def combinationSum(self, candidatos: List[int], target: int) -> List[List[int]]:
   def dfs(sobrante, pila, resultado):
       if not sobrante:
           resultado.append(pila)
           return
       for numero in candidatos:
           if numero > sobrante:
               return
           if not pila or pila[-1] <= numero:
               dfs(sobrante - numero, pila + [numero], resultado)
   resultado = []
   candidatos.sort()
   dfs(target, [], resultado)
   return resultado

def permute(self, numeros):
   def dfs(listaNumeros, combinaciónActual, permutaciones):
       if not listaNumeros:
           permutaciones.append(combinaciónActual)
       for i in range(len(listaNumeros)):
           dfs(listaNumeros[:i]+listaNumeros[i+1:], combinaciónActual+[listaNumeros[i]], permutaciones)
   permutaciones = []
   dfs(numeros, [], permutaciones)
   return permutaciones

def letterCasePermutation(self, S: str) -> List[str]:
   res = []
   def dfs(permutacionActual, apuntador):
       if apuntador == len(S):
           res.append(''.join(permutacionActual))
           return
       for i in set([S[apuntador].lower(), S[apuntador].upper()]):
           permutacionActual.append(i)
           dfs(permutacionActual, apuntador+1)
           permutacionActual.pop()
   dfs([],0)
   return res

input_1A = [2,3,6,7]
input_1B = 7
output_1 =  [[2,2,3],[7]]

def create_combinations(options, target, current_combination, combinations, index=0):
    current_sum = 0
    for number in current_combination:
        current_sum += number
    if current_sum == target:
        combinations.append(current_combination[:])
        return
    if current_sum > target:
        return
    for i in range(index, len(options)):
        current_combination.append(options[i])
        create_combinations(options, target, current_combination, combinations, i)
        current_combination.pop()
    return

def sum_combinations(options, target):
    combinations = []
    create_combinations(options, target, [], combinations)
    return combinations
    

print(sum_combinations(input_1A, input_1B))
print(sum_combinations(input_1A, input_1B)==output_1)

input_1 = "a1b2"
output_1 = ["a1b2","a1B2","A1b2","A1B2"]
input_2 = "3z4" 
output_2 = ["3z4", "3Z4"]


def generate_combinations_recursively(base_string, combination, combinations, index=0):
    if len(combination) == len(base_string) and combination not in combinations:
        combinations.append(combination[:])
        return
    for i in range(index, len(base_string)):
        if base_string[i].isalpha():
            combination += base_string[i].lower()
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
            combination += base_string[i].upper()
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
        elif base_string[i].isdigit():
            combination += base_string[i]
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
    return combinations

def get_letter_combinations(string):
    letter_combinations = []
    generate_combinations_recursively(string, "", letter_combinations)
    return letter_combinations        

print(get_letter_combinations(input_2))
print(get_letter_combinations(input_1))
print(get_letter_combinations(input_1)==output_1)
print(get_letter_combinations(input_2)==output_2)

input_1 = [1,2,3] 
output_1 = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
input_2 = [0,1] 
output_2 = [[0,1],[1,0]]

def generate_permutations_recursively(numbers, permutation, permutations):
    if len(permutation) == len(numbers) and permutation not in permutations:
        permutations.append(permutation[:])
        return
    for number in numbers:
        if number not in permutation:
            permutation.append(number)
            generate_permutations_recursively(numbers, permutation, permutations)
            permutation.pop()
    return permutations

def get_permutations(numbers):
    permutations = []
    generate_permutations_recursively(numbers, [], permutations)
    return permutations        

print(get_permutations(input_1))
print(get_permutations(input_2))
print(get_permutations(input_1)==output_1)
print(get_permutations(input_2)==output_2)

input_1A = [2,3,6,7]
input_1B = 7
output_1 =  [[2,2,3],[7]]

def create_combinations(options, target, current_combination, combinations, index=0):
    current_sum = 0
    for number in current_combination:
        current_sum += number
    if current_sum == target:
        combinations.append(current_combination[:])
        return
    if current_sum > target:
        return
    for i in range(index, len(options)):
        current_combination.append(options[i])
        create_combinations(options, target, current_combination, combinations, i)
        current_combination.pop()
    return

def sum_combinations(options, target):
    combinations = []
    create_combinations(options, target, [], combinations)
    return combinations
    

print(sum_combinations(input_1A, input_1B))
print(sum_combinations(input_1A, input_1B)==output_1)

input_1 = "a1b2"
output_1 = ["a1b2","a1B2","A1b2","A1B2"]
input_2 = "3z4" 
output_2 = ["3z4", "3Z4"]


def generate_combinations_recursively(base_string, combination, combinations, index=0):
    if len(combination) == len(base_string) and combination not in combinations:
        combinations.append(combination[:])
        return
    for i in range(index, len(base_string)):
        if base_string[i].isalpha():
            combination += base_string[i].lower()
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
            combination += base_string[i].upper()
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
        elif base_string[i].isdigit():
            combination += base_string[i]
            generate_combinations_recursively(base_string, combination, combinations, i+1)
            combination = combination[:-1]
    return combinations

def get_letter_combinations(string):
    letter_combinations = []
    generate_combinations_recursively(string, "", letter_combinations)
    return letter_combinations        

print(get_letter_combinations(input_2))
print(get_letter_combinations(input_1))
print(get_letter_combinations(input_1)==output_1)
print(get_letter_combinations(input_2)==output_2)

input_1 = [1,2,3] 
output_1 = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
input_2 = [0,1] 
output_2 = [[0,1],[1,0]]

def generate_permutations_recursively(numbers, permutation, permutations):
    if len(permutation) == len(numbers) and permutation not in permutations:
        permutations.append(permutation[:])
        return
    for number in numbers:
        if number not in permutation:
            permutation.append(number)
            generate_permutations_recursively(numbers, permutation, permutations)
            permutation.pop()
    return permutations

def get_permutations(numbers):
    permutations = []
    generate_permutations_recursively(numbers, [], permutations)
    return permutations        

print(get_permutations(input_1))
print(get_permutations(input_2))
print(get_permutations(input_1)==output_1)
print(get_permutations(input_2)==output_2)

Combinaciones y Permutaciones con Backtracking

Introducción

Qué son los grafos y cómo modelan el mundo

Qué es un árbol en estructuras de datos

Qué es la recursión en programación

Grafos en el mundo real que ya conoces

Representación de Grafos: Matriz y Lista de Adyacencia

DFS

Cómo recorre nodos el algoritmo DFS

Implementación de DFS recursivo para búsqueda en árboles

Búsqueda en Profundidad (DFS) para Grafos: Enfoque Iterativo y Recursivo

Inorder, Preorder y Postorder en árboles

Suma de caminos raíz a hoja en árboles

Suma de caminos raíz a hoja con DFS

Playground: Sum Root to Leaf Numbers

Implementación de Algoritmo DFS en Árboles Binarios con Golang

Número de islas con DFS en matrices

Problema de islas resuelto con DFS

Playground: Number of Islands

Número de islas con DFS recursivo en Python

Ejercicios Prácticos de Búsqueda en Profundidad (DFS)

Algoritmos de Búsqueda en Profundidad (DFS) en Problemas Comunes

BFS

Cómo BFS recorre grafos por niveles

Implementación de BFS con colas en Python

Mínimos movimientos del caballo en ajedrez

Minimum Knight's Move con BFS

Playground: Minimum Knights Moves

Resolución de Problemas de Caballos de Ajedrez con BFS en Python

Propagación BFS en Rotting Oranges

Resolución de Rotting Oranges usando BFS

Playground: Rotting Oranges

Implementación de BFS para naranjas podridas

Puente más corto entre islas con BFS

Shortest Bridge: combina DFS y BFS

Playground: Shortest Bridge Between Islands

Shortest Bridge con DFS y BFS en Python

Búsqueda en anchura: Ejercicios prácticos y aplicaciones

Ejercicios avanzados de búsqueda en anchura (BFS) en programación

Backtrack

Backtracking para encontrar soluciones válidas

Combinaciones de letras en teclado telefónico

Combinaciones de teclado con backtracking

Generación de combinaciones de letras con teclados numéricos en C++

Playground: Letter Combinations of a Phone Number

Generación de Direcciones IP Válidas a partir de Cadenas Numéricas

Backtracking para generar IPs válidas

Playground: Restore IP Addresses

Búsqueda de Palabras en Matrices: Solución y Complejidad

Word Search con DFS y backtracking

Playgrund: Word Search

Búsqueda de palabras en matrices con DFS

Resolución del problema de las n reinas en ajedrez

Ejercicios de Backtracking: Combinaciones y Permutaciones

Combinaciones y Permutaciones con Backtracking

Próximos pasos

Dijkstra y topological sort en grafos

Qué sigue después de aprender grafos