13 · Backtracking

Buscar soluciones eficientes · Ruta de Aprendizaje

Antes de empezar. Llamadas recursivas de 09 - Recursión y vectores de 03 - Arreglos y búsqueda lineal.

🎯 Objetivos

Al terminar este módulo sabes:

  • Generar todos los subconjuntos, permutaciones y combinaciones con recursión.
  • Aplicar el patrón universal elegir → explorar → deshacer.
  • Podar, estimar si cabe en tiempo, y cosechar subtareas con fuerza bruta digna.

📖 La lección

El patrón universal

Tenemos dos elementos, 1 y 2, y queremos listar todos los grupos que podemos formar sin repetir una posición. Estos subconjuntos son {}, {2}, {1} y {1,2}: para cada elemento decidimos si entra o no. El vacío también cuenta.

Podemos organizar las decisiones en dos niveles: primero decidir sobre el 1; en cada una de sus dos opciones, decidir sobre el 2. No son cuatro recetas distintas: repetimos la misma pregunta con el elemento siguiente.

i indica qué posición falta decidir y actual guarda lo elegido antes. Cuando i=n, ya decidimos todas las posiciones y podemos imprimir el grupo. Al explorar la opción «tomar», agregamos el elemento; al volver, lo quitamos para recuperar exactamente el grupo anterior. Ese recorrido de decisiones con restauración se llama backtracking: elegir, explorar y deshacer.

Las variables y la función siguientes van antes de main:

int n;
vector<int> a, actual;   // globales: a es la entrada, actual el subconjunto en construcción
 
void subconjuntos(int i) {
    if (i == n) {
        cout << "{";
        for (int j = 0; j < (int)actual.size(); j++) {
            if (j > 0) cout << ",";
            cout << actual[j];
        }
        cout << "}\n";
        return;
    }
    subconjuntos(i + 1);      // EXPLORAR sin a[i]
    actual.push_back(a[i]);   // ELEGIR a[i]
    subconjuntos(i + 1);      // EXPLORAR con a[i]
    actual.pop_back();        // DESHACER (la clave del backtracking)
}

Después de leer a, asigna n = a.size(), vacía actual con actual.clear() y llama subconjuntos(0). Sin esa llamada, definir la función no inicia el recorrido.

El pop_back es lo que hace que la misma estructura sirva para las 2ⁿ ramas: al volver de una rama, el estado queda exactamente como estaba. Dibujado para {a, b, c}:

∅sin a∅sin b∅sin c∅con cccon bbsin cbcon cbccon aasin basin cacon caccon babsin cabcon cabci = 0: ¿entra a?i = 1: ¿entra b?i = 2: ¿entra c?i = 3: procesarcada nodo es una llamada; bajar por “con” hace push_back, y al volver, pop_back lo deshace8 hojas = 2³ subconjuntos; con n elementos, 2ⁿ

Si el diagrama no cabe, deslízalo horizontalmente.

Cada nodo es una llamada a subconjuntos(i), cada nivel una decisión, y las hojas son los 2³ = 8 resultados. Fíjate en el orden en que se generan (de izquierda a derecha): primero el vacío, y el conjunto completo al final — exactamente el orden del código, que explora “sin” antes que “con”.

En la hoja, el programa imprime actual. Con a={1,2}, la salida es {}, {2}, {1}, {1,2} en líneas separadas. Dentro de main, prepara a={1,2}; n=a.size(); actual.clear(); subconjuntos(0);.

Momento en la rama que elige 1actual
antes de elegir 2{1}
tras push_back(2){1,2}
al volver de imprimir la hoja{1,2}
tras pop_back(){1}

Volver de la llamada no deshace automáticamente los cambios del vector compartido: por eso existe el último paso. Para contar subconjuntos que suman un objetivo, en la hoja suma sus valores e incrementa un contador solo si coincide. En {1,2}, el objetivo 2 tiene una solución: {2}.

Las decisiones son sobre posiciones: si la entrada es {1,1}, hay dos formas de elegir un solo elemento, aunque impriman el mismo valor. Para pedir resultados únicos, hay que evitar ramas equivalentes (por ejemplo, ordenar y omitir elecciones repetidas en el mismo nivel).

Una combinación de tamaño k es un subconjunto con exactamente k miembros: basta procesar solo las hojas donde actual.size() == k. Para {1, 2, 3} y k = 2, son {1, 2}, {1, 3}, {2, 3}; el orden dentro de cada grupo no crea otra combinación. En una permutación sí importa.

Permutaciones (con memoria de lo usado)

Ahora queremos ordenar todos los números de 1 a n, usando cada uno una vez. Una permutación es uno de esos órdenes: con n = 3, 1,2,3 y 2,1,3 son respuestas distintas. A diferencia de los subconjuntos, no decidimos «entra o no entra», sino quién ocupa la próxima posición.

perm guarda el comienzo del orden que estamos construyendo. usado[x] dice si x ya aparece en ese comienzo, para no elegirlo dos veces. Si el comienzo es [1], podemos probar 2 o 3, pero no otro 1.

Solo la rama que empieza por 1[1]elegir 2[1, 2]elegir 3[1, 2, 3]elegir 3[1, 3]elegir 2[1, 3, 2]Entre las ramas, volvemos a [1]:quitamos 3 y luego 2, liberando sus marcas.Las ramas que empiezan en 2 y 3 no se muestran.

Si el diagrama no cabe, deslízalo horizontalmente.

La figura muestra solo la rama que empieza por 1. Tras imprimir [1,2,3], volver no vacía el vector automáticamente: quitamos el 3 y liberamos su marca; después quitamos el 2 y liberamos la suya. Así regresamos a [1] y podemos probar 3 como segundo número. Deshacer ambas cosas restablece las opciones que tenía la llamada antes de explorar esa rama.

Estas variables y la función van antes de main:

int n;
vector<int> perm;
vector<bool> usado;   // globales; usado.assign(n + 1, false) antes de llamar
 
void permutaciones() {
    if ((int)perm.size() == n) {
        for (int x : perm) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int x = 1; x <= n; x++) {
        if (usado[x]) continue;          // poda: no repetir
        usado[x] = true; perm.push_back(x);
        permutaciones();
        perm.pop_back(); usado[x] = false; // deshacer
    }
}

En este segundo ejemplo, fija n, ejecuta usado.assign(n + 1, false) y perm.clear(), y llama permutaciones(). Se ordenan los números 1..n; para n = 2 se generan 1, 2 y 2, 1. Para n = 3, el código imprime, en orden: 123, 132, 213, 231, 312, 321 (aquí omitimos los espacios).

Por qué están todas y no se repiten. Cada posición prueba todos los números que aún faltan. Cualquier orden válido elige una de esas ramas en cada nivel; dos caminos distintos difieren en alguna posición. Hay n opciones para el primer puesto, n−1 para el segundo, etc.: n! resultados. Imprimirlos completos requiere O(n·n!) tiempo; perm, usado y las llamadas ocupan O(n) memoria adicional si no guardamos todas las respuestas.

La ficha de referencia con las dos plantillas juntas es Backtracking.

Podar: el arte de no explorar lo inútil

Una poda corta ramas que ya no pueden llevar a una solución: si la suma parcial ya se pasó del objetivo (con valores no negativos), retorna de inmediato; en N-reinas, no sigas si la reina recién puesta ya se ataca. Una buena poda convierte un árbol imposible en uno que vuela.

con 5sin 5con 4sin 4con 4sin 405095409 > 6: se podaFalta decidir sobre el 3: agregarlo tampoco reduce la suma.los números son la suma parcial; el objetivo es 6

Si el diagrama no cabe, deslízalo horizontalmente.

La poda no cambia la respuesta, solo evita trabajo: todo lo que colgaba de la rama podada habría fallado igual. Cuanto más arriba podes, más te ahorras.

¿Cabe en tiempo?

Cuenta tanto las soluciones como el trabajo de procesarlas. Para n elementos hay 2ⁿ subconjuntos, pero imprimir cada uno puede requerir hasta n valores: O(n·2ⁿ) en total. Para permutaciones hay n! órdenes y escribirlos requiere O(n·n!). Con n=10 hay 3628800 permutaciones: imprimirlas ya significa más de 36 millones de números.

Una subtarea de entrada pequeña invita a estimar una enumeración, pero no asegura puntos: hay que comprobar su tiempo, memoria y condiciones. Una poda puede ahorrar trabajo sin mejorar necesariamente el peor caso. Usa el conteo y la medición de 07 - Cuánto se demora tu programa.

El puente que viene

Dos llamadas con el mismo índice no siempre son el mismo subproblema: pueden traer distintos elementos en actual. Para reutilizar resultados, el estado debe describir toda la información que afecta la respuesta. Cuando esos estados sí se repiten, anotar resultados (la memoización del módulo 09) transforma el backtracking en otra cosa: la programación dinámica del próximo módulo.

🏋️ Práctica

Práctica directa: Enumerar y contar

Con los valores {1,2,3}, imprime los ocho subconjuntos y cuenta los que suman 3. El conteo debe ser 2: {3} y {1,2}.

Variación: Distinguir posiciones

Enumera subconjuntos de posiciones de {2,2,3} cuya suma sea 4. Cada posición se usa a lo más una vez. ¿Cuántos hay? ¿Qué cambiaría si el objetivo fuera 2?

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

Problemas OCI reales, en español (cada nota trae el link a su mirror):

#ProblemaFaseQué practica
1Las sumas de GabrielaRegional 2018probar cortes y verificar
2Cubos de papelNacional 2019enumerar las 24 rotaciones sin perder ninguna
3⭐ Jaque mateRegional 2020generar TODOS los movimientos legales

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Creating Strings (CSES 1622)★★ (—)permutaciones únicas de un string
2Apple Division (CSES 1623)★★ (—)subconjuntos 2ⁿ minimizando diferencia
3Chessboard and Queens (CSES 1624)★★★ (—)poda estilo N-reinas con casillas prohibidas
4⭐ Petr and a Combination Lock (1097B)★★★ (1200)2ⁿ decisiones (+/−) módulo 360

Para pensar: cuándo una poda pierde soluciones

Buscas un subconjunto que sume 6. Ya elegiste 9 y todavía queda el elemento −3. ¿Es válida la poda «si la suma supera 6, abandonar esta rama»?


← 12 - Búsqueda binaria sobre la respuesta · Ruta de Aprendizaje · 14 - Programación dinámica I →