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
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.

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.
• 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:

85 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Árboles.
• DFS/BFS por niveles.
• Validación de BST.
• Lowest common ancestor.

Primeros problemas sugeridos:

• Maximum Depth of Binary Tree.
• Invert Binary Tree.
• Diameter of Binary Tree.
• Balanced Binary Tree.
• Binary Tree Level Order Traversal.