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}:
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 1 | actual |
|---|---|
| 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.
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.
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}.
Idea para comprobar tu solución
Cada posición tiene dos decisiones. Evalúa la suma en la hoja y restaura actual al volver; elegir dos posiciones distintas con el mismo valor sería otra variante.
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?
Una pista, si la necesitas
Los dos valores 2 son iguales, pero sus posiciones son distintas.
Contrastar el razonamiento
Hay un subconjunto para suma 4: las dos primeras posiciones. Para suma 2 hay dos. En cada paso decide tomar o no tomar una posición; evita confundir contar posiciones con eliminar valores duplicados.
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):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Las sumas de Gabriela | Regional 2018 | probar cortes y verificar |
| 2 | Cubos de papel | Nacional 2019 | enumerar las 24 rotaciones sin perder ninguna |
| 3 | ⭐ Jaque mate | Regional 2020 | generar TODOS los movimientos legales |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Creating Strings (CSES 1622) | ★★ (—) | permutaciones únicas de un string |
| 2 | Apple Division (CSES 1623) | ★★ (—) | subconjuntos 2ⁿ minimizando diferencia |
| 3 | Chessboard 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»?
Ver razonamiento
No: elegir −3 completa la solución
{9, −3}. La poda solo es válida si todos los elementos pendientes son no negativos: entonces ninguna decisión futura puede reducir la suma. Podar exige demostrar que ninguna continuación sirve; que el estado actual no sea una solución no basta. Al volver de esta rama, también hay que deshacer el 9 para explorar las alternativas con el estado original.
← 12 - Búsqueda binaria sobre la respuesta · Ruta de Aprendizaje · 14 - Programación dinámica I →