Semanas 7 y 8 Recursion Backtracking y Linked Lists

Semanas 7 y 8: Recursión, Backtracking y Listas Enlazadas

Objetivo

Construir soluciones recursivas claras, practicar árboles de decisión y manejar listas enlazadas en Rust con ownership explícito.

Problemas Completados

Problema	Patrón	Función	Tests
Subsets	Backtracking de decisión	subsets	2
Permutations	Backtracking con marcadores	permute	2
Combination Sum	Backtracking con pruning	combination_sum	2
Generate Parentheses	Backtracking restringido	generate_parentheses	2
Word Search	DFS en matriz	word_search	2
Combination Sum II	Backtracking con duplicados	combination_sum_ii	2
Palindrome Partitioning	Cortes con validación local	palindrome_partitioning	2
Letter Combinations of a Phone Number	Producto cartesiano	letter_combinations	2
N-Queens	Backtracking con restricciones	n_queens_solutions	2
Subsets II	Subconjuntos con duplicados	subsets_with_dup	2
Reverse Linked List	Rewire iterativo	reverse_list	2
Merge Two Sorted Lists	Recursión sobre menor cabeza	merge_two_lists	2
Linked List Cycle	Fast/slow pointers	has_cycle	2
Reorder List	Intercalado front/back	reorder_list	2

Ideas Clave

Backtracking

Backtracking explora un árbol de decisiones y revierte cada decisión al volver.

Preguntas útiles:

• ¿Cuál es el estado actual?
• ¿Qué opciones existen desde este estado?
• ¿Cuál es la condición de parada?
• ¿Qué se debe deshacer al regresar?

Pruning

En combination_sum, ordenar candidatos permite cortar la rama cuando el candidato ya supera el restante.

Invariante:

• Si candidate > remaining, los siguientes candidatos también serán demasiado grandes.

Duplicados por Nivel

En combination_sum_ii y subsets_with_dup, ordenar permite saltar valores repetidos en la misma profundidad.

Invariante:

• Si index > start y el valor actual es igual al anterior, esa rama produciría una combinación ya emitida.
• El salto se hace por nivel, no globalmente, para no perder combinaciones válidas.

Cortes de Palíndromos

En palindrome_partitioning, cada corte se acepta solo si el segmento actual es palíndromo.

Invariante:

• El camino contiene particiones válidas del prefijo ya consumido.
• Al llegar al final, el camino completo cubre toda la cadena.

Restricciones de N-Queens

En n_queens_solutions, una reina por fila basta; las colisiones se validan con columnas y diagonales.

Invariante:

• row + col identifica una diagonal descendente.
• row + n - 1 - col identifica una diagonal ascendente.

DFS en Matriz

En word_search, cada celda puede usarse una sola vez por camino.

Invariante:

• La celda actual se marca como visitada antes de explorar vecinos.
• La celda se restaura al terminar esa rama.

Listas Enlazadas en Rust

Rust obliga a hacer explícita la propiedad de nodos con Option<Box<ListNode>>.

Ideas clave:

• take() permite mover el next sin clonar el nodo.
• Reverse list se resuelve moviendo nodos hacia una nueva cabeza.
• Merge list se puede expresar recursivamente eligiendo la cabeza menor.
• Para estudiar ciclos de forma segura, se usó representación de índices: Vec<Option<usize>>.

Errores Comunes

• Olvidar hacer pop() después de una decisión de backtracking.
• No clonar el camino antes de guardarlo en resultados.
• Reutilizar celdas en word_search.
• Saltar duplicados globalmente y perder combinaciones válidas.
• En N-Queens, revisar todo el tablero cuando bastan columnas y diagonales.
• En particiones de palíndromos, aceptar un corte no palíndromo y corregirlo después.
• Perder ownership al manipular Option<Box<ListNode>>.
• Intentar modelar ciclos reales con Box sin una estrategia segura.

Verificación

cargo test

Resultado al cerrar el bloque:

433 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Geometría.
• Matrices.
• Selección final del hito 190.

Primeros problemas sugeridos:

• Rotate Image.
• Spiral Matrix.
• Set Matrix Zeroes.
• Valid Sudoku.