Sesión 37: CTCI Capítulo 8 (Parte 1) — Backtracking Fundamental: Subconjuntos y Paréntesis (CTCI 8.4 & 8.9)#

Navegación rápida:

• ← Sesión 36: Grokking Ch8 — Greedy, Set Cover e Interval Scheduling
• Sesión 38: CTCI Ch8 — Backtracking: Permutaciones y N-Reinas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_37.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión inauguramos el estudio de los algoritmos de búsqueda combinatoria sistemática mediante Vuelta Atrás (Backtracking), analizando el manejo óptimo del estado mutable en memoria y la poda temprana de ramas inválidas. Consulta el Glosario Maestro y la Guía de Diagramas.

Árbol de Decisiones y Vuelta Atrás (Backtracking)#

• (a) En palabras simples (intuición): Entrar a un laberinto con un ovillo de hilo y un lápiz. En cada bifurcación eliges el camino izquierdo y vas soltando hilo. Si llegas a un callejón sin salida, te detienes de inmediato, enrollas el hilo caminando hacia atrás hasta la bifurcación anterior, marcas con el lápiz "por aquí no es" y tomas el camino derecho.
• (b) Definición técnica paso a paso: Estrategia de búsqueda exhaustiva en profundidad (DFS) que explora el espacio de soluciones de un problema construyendo candidatos de forma incremental. Al descubrir que un prefijo actual viola las restricciones o no puede completarse en una solución válida, detiene la exploración de todo el subárbol (poda) y deshace la última decisión para probar la siguiente alternativa.
• (c) Cómo funciona en Rust (memoria y tipos): Utiliza un único vector mutable &mut Vec<T> pasado por referencia mutable a través del Call Stack de llamadas recursivas.
• (d) Error típico de Junior: Clonar el vector completo en cada llamada recursiva (path.clone()), creando miles de asignaciones redundantes en el Heap que saturan el asignador de memoria y disparan el tiempo de ejecución.

Invariante Push-Recurse-Pop en Búfer Único#

• (a) En palabras simples (intuición): Probarse sombreros frente al espejo. No compras un perchero nuevo para cada sombrero que te pruebas: tomas el sombrero de la caja (Push), te miras al espejo (Recurse), te quitas el sombrero y lo regresas a la caja (Pop), dejando tu cabeza exactamente como estaba antes de probarte el siguiente sombrero.
• (b) Definición técnica paso a paso: Protocolo estricto de mutación y restauración de estado en backtracking:

1. path.push(candidate): Aplica la decisión mutando el estado local.
2. backtrack(..., path, ...): Explora el subárbol recursivo.
3. path.pop(): Deshace de manera irrevocable la mutación, restaurando la invariante del llamador.

• (c) Cómo funciona en Rust (memoria y tipos): La capacidad del vector se reserva una sola vez con Vec::with_capacity(N). El método .push() y .pop() modifican únicamente la longitud interna (len) del vector en el Stack sin realocar memoria en el Heap. Únicamente se invoca .clone() cuando se alcanza una hoja válida que se inserta en results.
• (d) Error típico de Junior: Olvidar invocar path.pop() antes de salir de la iteración; el estado contaminado se propaga a las ramas hermanas, generando soluciones con elementos erróneos acumulados.

Poda en Tiempo de Construcción (Early Pruning)#

• (a) En palabras simples (intuición): Si estás escribiendo una ecuación matemática y pones un signo ) sin haber abierto ningún (, no terminas de escribir toda la hoja para darte cuenta del error: borras el paréntesis en ese mismo microsegundo.
• (b) Definición técnica paso a paso: Descarte inmediato de una rama del árbol de búsqueda en el instante exacto en que se detecta que no cumple las invariantes del problema, antes de descender en la recursión. En generación de paréntesis, jamás se genera una combinación inválida de antemano (close_count < open_count).
• (c) Cómo funciona en Rust (memoria y tipos): Condicionales guardias simples antes de las llamadas recursivas: if open_count < n { ... } y if close_count < open_count { ... }.
• (d) Error típico de Junior: Generar las 2^{2N} combinaciones binarias posibles a ciegas y filtrar al final con una función is_valid(), sufriendo una explosión temporal exponencial intratable (O(4^N · N) vs O(4^N / √(N))).

Poda de Ramas Hermanas Idénticas en Subconjuntos II#

• (a) En palabras simples (intuición): Si tienes dos manzanas idénticas en una canasta y decides no incluir la primera manzana en tu bolsa, sería una pérdida de tiempo preguntarte si quieres incluir la segunda manzana: el resultado sería una bolsa exactamente idéntica a la que ya evaluaste.
• (b) Definición técnica paso a paso: Técnica para omitir subconjuntos duplicados cuando el arreglo contiene valores repetidos (LC 90). Tras ordenar el arreglo numérico, si en el mismo nivel de iteración actual se observa que nums[i] == nums[i-1] y el índice i es estrictamente mayor que el punto de partida del nivel (i > start), se ignora esa iteración con continue.
• (c) Cómo funciona en Rust (memoria y tipos): Requiere ordenar previamente con sorted.sort_unstable(), garantizando que los duplicados queden físicamente contiguos en memoria RAM.
• (d) Error típico de Junior: Utilizar un HashSet<Vec<i32>> para eliminar duplicados al final; aunque matemáticamente funciona, gasta O(N · 2^N) tiempo y memoria calculando y desechando ramas enteras redundantes.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Arquitectura de Memoria del Backtracking en Rust: ¿Por Qué un Búfer Único?#

Supongamos que queremos generar todos los subconjuntos de un arreglo de tamaño N = 20. El número total de subconjuntos es:

Comparemos dos arquitecturas de implementación:

Enfoque 1: Clonación Funcional Inocente (path + [num])#

• En cada llamada del árbol de recursión, se crea un nuevo vector en el Heap y se clonan los elementos del camino acumulado.
• El número total de nodos en el árbol de recursión es:

• Cada asignación en el Heap requiere llamadas al sistema operativo (malloc/HeapAlloc), actualiza metadatos de fragmentación y destruye la línea de caché del procesador.
• Consumo de memoria adicional: más de 50 MB de asignaciones efímeras que saturan el recolector o la memoria RAM.

Enfoque 2: Búfer Mutable Único con Invariante Push/Pop (&mut Vec<T>)#

• Se reserva memoria para un único vector en el inicio:

  let mut current_path = Vec::with_capacity(n); // Solo 20 enteros = 80 bytes

• Al avanzar por una rama: current_path.push(x) solo incrementa el entero de longitud len en el Stack de la CPU (costo: 1 instrucción ensamblador, 0 asignaciones Heap).
• Al retroceder: current_path.pop() solo decrementa len (costo: 1 instrucción ensamblador).
• Únicamente se clona cuando se alcanza una solución válida:

  results.push(current_path.clone());

• Memoria auxiliar física consumida durante la búsqueda: exactamente 80 bytes en el Heap y 20 marcos en el Call Stack.

¡El rendimiento en silicio es entre 15 y 30 veces más veloz!

La Matemática de los Paréntesis Balanceados: Números de Catalan#

¿Cuántas secuencias válidas y bien balanceadas de N pares de paréntesis existen en total? El número está dictado formalmente por el n-ésimo Número de Catalan:

Evaluación para valores comunes en entrevistas:

• n = 1 ⟹ C₁ = 1: ["()"]
• n = 2 ⟹ C₂ = 2: ["(())", "()()"]
• n = 3 ⟹ C₃ = 5: ["((()))", "(()())", "(())()", "()(())", "()()()"]
• n = 4 ⟹ C₄ = 14
• n = 5 ⟹ C₅ = 42

Crecimiento asintótico:

Mientras que la fuerza bruta genera 2^{2n} = 4^n combinaciones posibles, el algoritmo de Backtracking guiado por contadores de apertura y cierre explora estrictamente el espacio de las Cₙ soluciones válidas, podando todas las ramas inviables en tiempo de construcción.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 37 y Memoria en Rust](../diagrams/sesiones/dia_37.svg)
• Código fuente del diagrama: Fuente Mermaid

Árbol de Estados y Poda en Generación de Paréntesis (n=2)#

flowchart TD
    ROOT["'' (open=0, close=0)"] --> O1["'(' (open=1, close=0)"]
    O1 --> O2["'((' (open=2, close=0)"]
    O1 --> C1["'()' (open=1, close=1)"]
    
    O2 --> C2["'(()' (open=2, close=1)"]
    C2 --> C3["'(())' [SOLUCIÓN 1]"]
    
    C1 --> O3["'()(' (open=2, close=1)"]
    O3 --> C4["'()()' [SOLUCIÓN 2]"]
    
    ROOT -.->|Poda: close >= open| X1["')' (Inválido)"]
    O2 -.->|Poda: open == n| X2["'(((' (Excede n)"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de subsets(&[1, 2, 3]) con búfer mutable compartido:

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame subsets                 |               | current_path: Vec<i32>               |
|   nums: &[1, 2, 3]            |               | Capacidad: 3, len: 0                 |
|   current_path: Vec<i32> -----+-------------->| [ _ , _ , _ ]                        |
|   results: Vec<Vec<i32>> -----+-------+       +--------------------------------------+
+-------------------------------+       +------>| results: Vec<Vec<i32>>               |
| Frame backtrack (start=0)     |               | [ [] ]                               |
+-------------------------------+               +--------------------------------------+

Paso 1: backtrack(0) -> guarda [] en results.
  - i=0: current_path.push(1) -> current_path: [1] (len=1)
  - Invoca backtrack(1)

Paso 2: Frame backtrack(1) -> guarda [1] en results.
  - i=1: current_path.push(2) -> current_path: [1, 2] (len=2)
  - Invoca backtrack(2)

Paso 3: Frame backtrack(2) -> guarda [1, 2] en results.
  - i=2: current_path.push(3) -> current_path: [1, 2, 3] (len=3)
  - Invoca backtrack(3)

Paso 4: Frame backtrack(3) -> guarda [1, 2, 3] en results.
  - Bucle for de i desde 3..3 no ejecuta. Retorna.

Paso 5: Frame backtrack(2) reanuda:
  - current_path.pop() -> len pasa a 2, el búfer ahora es [1, 2].
  - Bucle for termina. Retorna.

Paso 6: Frame backtrack(1) reanuda:
  - current_path.pop() -> len pasa a 1, el búfer ahora es [1].
  - Bucle for avanza a i=2: current_path.push(3) -> búfer [1, 3].
  - Invoca backtrack(3)...

¡El mismo búfer físico de 3 enteros es reutilizado a lo largo de las 16 llamadas del árbol!

4. Las 3 Trampas Clásicas en Entrevistas#

1. Olvidar Clonar al Almacenar en Resultados: - En Python o JavaScript, escribir results.append(current_path) sin .clone() o list() almacena una referencia mutable. Al terminar el algoritmo, current_path queda vacío y results contendrá únicamente listas vacías. En Rust, el compilador te obligará a usar .clone() porque results toma posesión de los datos.
2. Generar Duplicados en Subsets II (LC 90): - Olvidar ordenar el arreglo antes de comenzar, o formular mal la condición de poda. La condición correcta es if i > start && nums[i] == nums[i-1] { continue; }. Si escribes i > 0, podarás combinaciones válidas que usan duplicados legítimos en distintas profundidades (como [2, 2]).
3. No Respetar la Invariante de Paréntesis: - Intentar validar combinaciones completas al final con una función is_valid() separada. Generar todas las cadenas posibles toma tiempo exponencial O(4^N · N). Validar en tiempo de inserción (open < n y close < open) asegura que el árbol solo visite combinaciones 100% correctas.

5. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (practica-rust/dia_37.rs)#

//! Día 37: Backtracking Fundamental: Subconjuntos y Paréntesis en Rust.

/// LeetCode 78: Subsets I con Backtracking in-place en O(N * 2^N).
pub fn subsets(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut results = Vec::with_capacity(1 << nums.len());
    let mut current_path = Vec::with_capacity(nums.len());

    fn backtrack(start: usize, nums: &[i32], path: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        results.push(path.clone());

        for i in start..nums.len() {
            path.push(nums[i]);
            backtrack(i + 1, nums, path, results);
            path.pop(); // Invariante: deshacer decisión
        }
    }

    backtrack(0, nums, &mut current_path, &mut results);
    results
}

/// LeetCode 90: Subsets II con duplicados y poda canónica de ramas hermanas.
pub fn subsets_with_dup(nums: &[i32]) -> Vec<Vec<i32>> {
    let mut sorted = nums.to_vec();
    sorted.sort_unstable();

    let mut results = Vec::new();
    let mut current_path = Vec::with_capacity(nums.len());

    fn backtrack(start: usize, nums: &[i32], path: &mut Vec<i32>, results: &mut Vec<Vec<i32>>) {
        results.push(path.clone());

        for i in start..nums.len() {
            if i > start && nums[i] == nums[i - 1] {
                continue; // Poda de rama hermana duplicada
            }
            path.push(nums[i]);
            backtrack(i + 1, nums, path, results);
            path.pop();
        }
    }

    backtrack(0, &sorted, &mut current_path, &mut results);
    results
}

/// LeetCode 22: Generate Parentheses guiado por contadores en O(4^n / sqrt(n)).
pub fn generate_parentheses(n: usize) -> Vec<String> {
    if n == 0 {
        return Vec::new();
    }

    let mut results = Vec::new();
    let mut current = String::with_capacity(2 * n);

    fn backtrack(open_c: usize, close_c: usize, n: usize, path: &mut String, res: &mut Vec<String>) {
        if path.len() == 2 * n {
            res.push(path.clone());
            return;
        }

        if open_c < n {
            path.push('(');
            backtrack(open_c + 1, close_c, n, path, res);
            path.pop();
        }

        if close_c < open_c {
            path.push(')');
            backtrack(open_c, close_c + 1, n, path, res);
            path.pop();
        }
    }

    backtrack(0, 0, n, &mut current, &mut results);
    results
}

Implementación Canónica en Python (practica/dia_37_backtracking_subsets_parens.py)#

from typing import List

def subsets_backtracking(nums: List[int]) -> List[List[int]]:
    """CTCI 8.4: Power Set con Backtracking in-place O(N * 2^N)."""
    result: List[List[int]] = []
    current: List[int] = []

    def backtrack(start: int) -> None:
        result.append(list(current))
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return result

def subsets_with_dup(nums: List[int]) -> List[List[int]]:
    """LC 90: Subsets II con duplicados y poda de ramas hermanas."""
    result: List[List[int]] = []
    current: List[int] = []
    sorted_nums = sorted(nums)

    def backtrack(start: int) -> None:
        result.append(list(current))
        for i in range(start, len(sorted_nums)):
            if i > start and sorted_nums[i] == sorted_nums[i - 1]:
                continue
            current.append(sorted_nums[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return result

def generate_parentheses(n: int) -> List[str]:
    """CTCI 8.9: Paréntesis bien formados con números de Catalan."""
    result: List[str] = []
    current: List[str] = []

    def backtrack(open_c: int, close_c: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return

        if open_c < n:
            current.append("(")
            backtrack(open_c + 1, close_c)
            current.pop()

        if close_c < open_c:
            current.append(")")
            backtrack(open_c, close_c + 1)
            current.pop()

    backtrack(0, 0)
    return result

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 78 — Subsets (Medium): - Power Set clásico con búfer mutable compartido.
2. LeetCode 90 — Subsets II (Medium): - Subconjuntos con duplicados y poda de ramas hermanas idénticas.
3. LeetCode 22 — Generate Parentheses (Medium): - Backtracking guiado por contadores de prefijo y números de Catalan.
4. LeetCode 39 — Combination Sum (Medium): - Combinaciones con elementos reutilizables y poda por cota numérica.

8. Tarea en Papel para Hoy#

Toma una hoja en blanco y tu lápiz:

1. Dibuja el árbol de llamadas completo de generate_parentheses(n=3): - Anota en cada rama qué opción se toma (( o )). - Marca con una cruz roja las ramas que son podadas en tiempo de construcción. - Enumera las 5 combinaciones hojas alcanzadas y verifica que coincidan con C₃ = 5.
2. Escribe la traza de ejecución de subsets_with_dup(&[1, 2, 2]), mostrando en qué paso exacto la condición i > start && nums[i] == nums[i-1] evita generar duplicados.

Navegación:

• ← Volver a Sesión 36: Grokking Ch8 — Greedy, Set Cover e Interval Scheduling
• Avanzar a Sesión 38: CTCI Ch8 — Backtracking: Permutaciones y N-Reinas →