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.

🔗 Relacionados