Backtracking
Tema: Constructivos y Ad-hoc · temarios: Syllabus OCI · Syllabus IOI
📍 Dónde se aprende: módulo 13 de la Ruta de Aprendizaje.
Qué hace
Recorre sistemáticamente todas las opciones construyendo la solución paso a paso y deshaciendo al retroceder. Es la fuerza bruta bien organizada: genera subconjuntos, permutaciones o combinaciones.
Complejidad: Depende de lo que genere: 2^n subconjuntos (n ≤ 20-25), n! permutaciones (n ≤ 10-11). Las podas bajan mucho el caso real.
Cuándo usarlo
Cuando n es chico, o para asegurar las subtareas pequeñas de un problema grande mientras piensas la solución de verdad. Módulo 13 de la Ruta de Aprendizaje.
Implementación recomendada (C++)
int N; vector<int> perm; vector<bool> usado;
void permutaciones() {
if ((int)perm.size() == N) { /* procesar perm */ return; } // caso base
for (int x = 1; x <= N; x++) {
if (usado[x]) continue; // poda: x ya está en la permutación
usado[x] = true; perm.push_back(x); // ELEGIR
permutaciones(); // EXPLORAR
perm.pop_back(); usado[x] = false; // DESHACER
}
}
// subconjuntos: por cada elemento, la decisión es entrar o no entrar
void subconjuntos(int i, vector<int>& actual, const vector<int>& a) {
if (i == (int)a.size()) { /* procesar actual */ return; }
subconjuntos(i + 1, actual, a); // sin a[i]
actual.push_back(a[i]); // ELEGIR a[i]
subconjuntos(i + 1, actual, a);
actual.pop_back(); // DESHACER
}⚠️ Notas
El pop_back/usado = false es el corazón: al volver de una rama, el estado queda exactamente como estaba. Podar temprano es lo que separa un backtracking usable de uno inútil: si la suma parcial ya se pasó (con valores no negativos), retorna sin seguir. Si el árbol de llamadas repite subproblemas, el paso siguiente es memoizar y ya estás en programación dinámica.