Backtracking en C#: subconjuntos, permutaciones y N reinas

El backtracking es el patrón con el núcleo más pequeño y el alcance más amplio. Todos los problemas de aquí son las mismas tres líneas con una regla de ramificación distinta.

choose      — add to the current state
explore     — recurse
un-choose   — take it back out

Los caminos de raíz a hoja de la parte 13 ya lo usaban. Esta parte es aquello para lo que existe.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la corrida.

Patrón 71 — Subconjuntos

Todos los subconjuntos de un conjunto. Para cada elemento hay dos opciones, así que la búsqueda es un árbol binario de n niveles de profundidad.

int[] a = [1, 2, 3];
List<List<int>> all = [];
List<int> current = [];

// The template every problem in this part is an instance of:
//   record the state, try each choice, UNDO the choice.
void Explore(int start, int depth)
{
    all.Add([.. current]);       // a copy — `current` keeps changing under us
    Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]");

    for (int i = start; i < a.Length; i++)
    {
        current.Add(a[i]);            // choose
        Explore(i + 1, depth + 1);    // explore, from AFTER i so nothing repeats
        current.RemoveAt(current.Count - 1);   // un-choose
    }
}

Explore(0, 0);
Console.WriteLine($"\n{all.Count} subsets, expected 2^{a.Length} = {1 << a.Length}");

// The same thing without recursion: each bit of a counter says include or not.
Console.WriteLine("\nby bitmask, no recursion at all:");
for (int mask = 0; mask < (1 << a.Length); mask++)
{
    var pick = Enumerable.Range(0, a.Length).Where(i => (mask & (1 << i)) != 0).Select(i => a[i]);
    Console.WriteLine($"  {Convert.ToString(mask, 2).PadLeft(a.Length, '0')} -> [{string.Join(",", pick)}]");
}

Imprime:

[]
  [1]
    [1,2]
      [1,2,3]
    [1,3]
  [2]
    [2,3]
  [3]

8 subsets, expected 2^3 = 8

by bitmask, no recursion at all:
  000 -> []
  001 -> [1]
  010 -> [2]
  011 -> [1,2]
  100 -> [3]
  101 -> [1,3]
  110 -> [2,3]
  111 -> [1,2,3]

Dos detalles cargan con todo el peso.

all.Add([.. current]) copia. current es una sola lista que se sigue mutando, así que guardar una referencia a ella significa que cada entrada de all termina apuntando al mismo objeto — y al final ese objeto está vacío. El spread de la expresión de colección es la copia.

El registro ocurre en cada nodo, no en las hojas. Un subconjunto no es «un camino completo hasta el fondo», es cualquier nodo del árbol, y por eso all.Add va antes del bucle y no dentro de un caso base.

La versión con máscara de bits del final es la misma enumeración sin recursión, y conecta con el patrón 45 de la parte 9. Para subconjuntos en particular suele ser la mejor respuesta — sin pila, sin deshacer, y los bits son las decisiones de incluir o excluir.

Costo: O(2ⁿ) subconjuntos, O(n · 2ⁿ) para escribirlos todos.

Úsalo cuando el problema pide todos los subconjuntos, el conjunto potencia, o todas las combinaciones de cualquier tamaño.

Patrón 72 — Permutaciones

Todos los órdenes posibles. Hay n!, así que esto solo es viable para n pequeño.

La implementación obvia mantiene un arreglo used[] y construye una lista nueva por rama. La versión con intercambios no necesita ninguna de las dos.

int[] a = [1, 2, 3];
List<string> all = [];

// Swap the chosen element into position, recurse on the rest, swap it back.
// No "used" array, no allocation per branch.
void Permute(int k, int depth)
{
    if (k == a.Length)
    {
        all.Add(string.Join(",", a));
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", a)}]  <- complete");
        return;
    }

    for (int i = k; i < a.Length; i++)
    {
        (a[k], a[i]) = (a[i], a[k]);            // choose: a[i] goes to position k
        Console.WriteLine($"{new string(' ', depth * 2)}position {k} := {a[k]}   array now [{string.Join(",", a)}]");
        Permute(k + 1, depth + 1);
        (a[k], a[i]) = (a[i], a[k]);            // un-choose: put it back
    }
}

Permute(0, 0);
Console.WriteLine($"\n{all.Count} permutations, expected {a.Length}! = {Enumerable.Range(1, a.Length).Aggregate(1, (x, y) => x * y)}");
Console.WriteLine($"array restored to its original order: [{string.Join(",", a)}]");

Imprime:

position 0 := 1   array now [1,2,3]
  position 1 := 2   array now [1,2,3]
    position 2 := 3   array now [1,2,3]
      [1,2,3]  <- complete
  position 1 := 3   array now [1,3,2]
    position 2 := 2   array now [1,3,2]
      [1,3,2]  <- complete
position 0 := 2   array now [2,1,3]
  position 1 := 1   array now [2,1,3]
    position 2 := 3   array now [2,1,3]
      [2,1,3]  <- complete
  position 1 := 3   array now [2,3,1]
    position 2 := 1   array now [2,3,1]
      [2,3,1]  <- complete
position 0 := 3   array now [3,2,1]
  position 1 := 2   array now [3,2,1]
    position 2 := 1   array now [3,2,1]
      [3,2,1]  <- complete
  position 1 := 1   array now [3,1,2]
    position 2 := 2   array now [3,1,2]
      [3,1,2]  <- complete

6 permutations, expected 3! = 6
array restored to its original order: [1,2,3]

Intercambia el elemento elegido a la posición k, recurre en k+1, y luego intercámbialo de vuelta. La posición k ya está decidida; todo desde k en adelante sigue disponible, en algún orden.

La última línea de esa salida es la verificación que vale la pena conservar: el arreglo vuelve a su orden original cuando todo termina. Si no lo hace, falta un deshacer en algún lado — y eso es mucho más fácil de detectar que una permutación equivocada enterrada en una lista de cientos.

La versión con intercambios no produce las permutaciones en orden lexicográfico, y la salida lo muestra. Si el problema pide la salida ordenada, ordénala después o usa la versión con used[].

Costo: O(n!) resultados, O(n) de espacio extra.

Úsalo cuando el problema trata de órdenes, acomodos o generación de anagramas.

Patrón 73 — Poda

El backtracking por sí solo es búsqueda exhaustiva. La poda es lo que lo vuelve usable, y ahí están las ganancias de verdad.

int[] candidates = [2, 3, 6, 7];
int target = 7;

Array.Sort(candidates);          // sorting is what makes the pruning possible
List<List<int>> found = [];
List<int> current = [];
int calls = 0, pruned = 0;

void Search(int start, int remaining, int depth)
{
    calls++;
    if (remaining == 0)
    {
        found.Add([.. current]);
        Console.WriteLine($"{new string(' ', depth * 2)}[{string.Join(",", current)}]  <- sums to {target}");
        return;
    }

    for (int i = start; i < candidates.Length; i++)
    {
        if (candidates[i] > remaining)
        {
            // Sorted, so every candidate after this one is bigger too.
            pruned += candidates.Length - i;
            Console.WriteLine($"{new string(' ', depth * 2)}{candidates[i]} > {remaining}, and the rest are larger -> prune {candidates.Length - i} branches");
            break;
        }
        current.Add(candidates[i]);
        Search(i, remaining - candidates[i], depth + 1);   // i, not i+1: reuse allowed
        current.RemoveAt(current.Count - 1);
    }
}

Search(0, target, 0);
Console.WriteLine($"\nsolutions: {string.Join("  ", found.Select(f => "[" + string.Join(",", f) + "]"))}");
Console.WriteLine($"recursive calls: {calls}, branches pruned: {pruned}");
Console.WriteLine($"\nSearch(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.");
Console.WriteLine($"Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.");

Imprime:

      2 > 1, and the rest are larger -> prune 4 branches
      [2,2,3]  <- sums to 7
    6 > 3, and the rest are larger -> prune 2 branches
    3 > 2, and the rest are larger -> prune 3 branches
  6 > 5, and the rest are larger -> prune 2 branches
    3 > 1, and the rest are larger -> prune 3 branches
  6 > 4, and the rest are larger -> prune 2 branches
  6 > 1, and the rest are larger -> prune 2 branches
  [7]  <- sums to 7

solutions: [2,2,3]  [7]
recursive calls: 10, branches pruned: 18

Search(i, ...) rather than Search(i + 1, ...) lets a candidate repeat.
Starting at i rather than 0 is what stops [2,2,3] and [2,3,2] both appearing.

Ordenar los candidatos primero es lo que hace posible la poda. Una vez que candidates[i] > remaining, todos los candidatos posteriores también son más grandes, así que el resto del bucle se puede abandonar con break en vez de continue. Dieciocho ramas nunca exploradas, con una entrada de cuatro números.

Dos detalles de índices, y son distintos entre sí:

• Search(i, ...) en vez de Search(i + 1, ...) permite reutilizar un candidato, que es lo que hace legal [2,2,3] aquí.
• Empezar el bucle en start en vez de en 0 es lo que evita que se reporten [2,2,3] y [2,3,2] a la vez. Las combinaciones no tienen orden; solo se generan secuencias no decrecientes.

Costo: exponencial en el peor caso, y a menudo mucho mejor. La poda es el algoritmo.

Úsalo cuando la forma es una búsqueda exhaustiva pero el árbol completo es demasiado grande — suma de combinaciones, particiones, problemas de restricciones.

Patrón 74 — Duplicados en la entrada

Dado [1, 2, 2], reporta cada subconjunto distinto una sola vez.

int[] a = [1, 2, 2];
Array.Sort(a);                    // duplicates must be ADJACENT for the skip to work

static List<string> Subsets(int[] a, bool skipDuplicates)
{
    List<string> all = [];
    List<int> current = [];

    void Explore(int start)
    {
        all.Add("[" + string.Join(",", current) + "]");
        for (int i = start; i < a.Length; i++)
        {
            // At this level, a repeated value would rebuild a branch already done.
            // i > start is the key: the FIRST 2 at a level is fine, the second is not.
            if (skipDuplicates && i > start && a[i] == a[i - 1]) continue;
            current.Add(a[i]);
            Explore(i + 1);
            current.RemoveAt(current.Count - 1);
        }
    }
    Explore(0);
    return all;
}

var naive = Subsets(a, false);
var fixed_ = Subsets(a, true);

Console.WriteLine($"input: [{string.Join(",", a)}]\n");
Console.WriteLine($"without the skip: {string.Join(" ", naive)}");
Console.WriteLine($"  {naive.Count} results, {naive.Distinct().Count()} of them distinct");
Console.WriteLine($"  repeated: {string.Join(" ", naive.GroupBy(x => x).Where(g => g.Count() > 1).Select(g => g.Key))}");

Console.WriteLine($"\nwith the skip:    {string.Join(" ", fixed_)}");
Console.WriteLine($"  {fixed_.Count} results, {fixed_.Distinct().Count()} of them distinct");

Console.WriteLine($"\ni > start, not i > 0. Using the second 2 as the FIRST pick at a level");
Console.WriteLine($"is a new branch; using it as a LATER pick repeats one already taken.");
Console.WriteLine($"That is a different bug from part 1's duplicate anchors, and it needs");
Console.WriteLine($"its own condition.");

Imprime:

input: [1,2,2]

without the skip: [] [1] [1,2] [1,2,2] [1,2] [2] [2,2] [2]
  8 results, 6 of them distinct
  repeated: [1,2] [2]

with the skip:    [] [1] [1,2] [1,2,2] [2] [2,2]
  6 results, 6 of them distinct

i > start, not i > 0. Using the second 2 as the FIRST pick at a level
is a new branch; using it as a LATER pick repeats one already taken.
That is a different bug from part 1's duplicate anchors, and it needs
its own condition.

Sin la omisión: ocho resultados, seis distintos, con [1,2] y [2] apareciendo dos veces cada uno.

La solución es if (i > start && a[i] == a[i - 1]) continue; sobre un arreglo ordenado. La condición lo es todo, y la comparación es contra start, no contra cero:

• En un nivel, elegir el segundo 2 reconstruye una rama que el primer 2 ya construyó. Omítelo.
• Más abajo, donde start ya pasó del primer 2, i == start y el segundo 2 es la primera elección en ese nivel — un subconjunto nuevo de verdad. Permítelo. Así es como sobrevive [2,2].

El 3Sum de la parte 1 también tenía un problema de duplicados, y era uno distinto — omitir anclas repetidas en un recorrido de dos punteros. Misma palabra, otro error, otra solución. Ninguna de las dos condiciones sirve para la otra.

Úsalo cuando la entrada puede tener repetidos y la salida no debe tenerlos.

Patrón 75 — N reinas

Coloca n reinas en un tablero de n × n de modo que ninguna ataque a otra.

int n = 4;
int[] col = new int[n];        // col[r] = which column the queen in row r sits in
List<string[]> solutions = [];
int placed = 0, rejected = 0;

bool Safe(int row, int c)
{
    for (int r = 0; r < row; r++)
    {
        if (col[r] == c) return false;                       // same column
        if (Math.Abs(col[r] - c) == row - r) return false;    // same diagonal
    }
    return true;
}

void Place(int row)
{
    if (row == n)
    {
        solutions.Add([.. Enumerable.Range(0, n).Select(r => new string('.', col[r]) + "Q" + new string('.', n - col[r] - 1))]);
        Console.WriteLine($"  solution: columns {string.Join(",", col)}");
        return;
    }

    for (int c = 0; c < n; c++)
    {
        if (!Safe(row, c)) { rejected++; continue; }
        col[row] = c;                 // choose
        placed++;
        Place(row + 1);               // explore
        // un-choose is implicit: col[row] is overwritten next iteration and
        // never read for rows >= the current one.
    }
}

Console.WriteLine($"{n}-queens:");
Place(0);

Console.WriteLine($"\n{solutions.Count} solutions");
foreach (var s in solutions)
{
    Console.WriteLine();
    foreach (string row in s) Console.WriteLine($"  {row}");
}

Console.WriteLine($"\nplacements tried: {placed}, rejected by Safe: {rejected}");
Console.WriteLine($"brute force would test {Math.Pow(n, n):N0} arrangements");
Console.WriteLine();
Console.WriteLine("One queen per row is built into the shape of the recursion, so that");
Console.WriteLine("constraint never has to be checked. Only columns and diagonals are.");

Imprime:

4-queens:
  solution: columns 1,3,0,2
  solution: columns 2,0,3,1

2 solutions

  .Q..
  ...Q
  Q...
  ..Q.

  ..Q.
  Q...
  ...Q
  .Q..

placements tried: 16, rejected by Safe: 44
brute force would test 256 arrangements

One queen per row is built into the shape of the recursion, so that
constraint never has to be checked. Only columns and diagonals are.

La decisión de diseño que vale la pena llevarse es que una reina por fila está integrada en la forma de la recursión. Place(row + 1) significa que cada llamada es dueña de exactamente una fila, así que «no hay dos reinas en la misma fila» es cierto por construcción y nunca se prueba.

Eso también colapsa el estado. El tablero no es una cuadrícula de n × n sino un int[n] — col[r] es donde está la reina de la fila r. Solo quedan dos comprobaciones: misma columna, y misma diagonal, que es Math.Abs(col[r] - c) == row - r.

No hay un deshacer explícito, y el comentario dice por qué: col[row] se sobrescribe en la siguiente iteración, y nada en la fila actual o por debajo se vuelve a leer. Cuando el deshacer no hace nada, vale la pena un comentario que lo diga — si no, el siguiente lector asume que se olvidó.

Costo: mucho mejor que los 256 acomodos que probaría la fuerza bruta, y aun así exponencial.

Úsalo cuando el problema es un rompecabezas de restricciones — Sudoku, sopa de letras, coloreado de grafos. Codificar una restricción en la forma de la recursión en vez de comprobarla es la jugada que hay que buscar siempre.

Qué recordar

• Elegir, explorar, deshacer. El deshacer es el que la gente deja fuera, y el código parece completo sin él.

• Copia el estado cuando lo registras. [.. current] — si no, cada resultado apunta a una sola lista que termina vacía.

• Los subconjuntos se registran en cada nodo, no en las hojas. El Add va antes del bucle.

• Comprueba que el estado quede restaurado al final. Un arreglo de permutación de vuelta en su orden original prueba que los deshacer están balanceados.

• Ordena antes de podar, y usa break en vez de continue. Una vez que un candidato es demasiado grande, en una lista ordenada todos lo son.

• i reutiliza un candidato; start evita duplicados reordenados. Dos decisiones de índice distintas que es fácil confundir.

• La omisión de duplicados es i > start, no i > 0. Contra start, para que el mismo valor todavía pueda ser la primera elección en un nivel más profundo.

• Integra las restricciones en la forma de la recursión cuando puedas. Una fila por llamada significa que la regla de la fila no necesita código.

La parte 16 es la última: manipulación de bits, que la serie viene usando desde la parte 3 sin decirlo nunca en voz alta.