Backtracking

Backtracking es búsqueda exhaustiva con poda inteligente. La idea: construye la solución paso a paso; si en algún punto la solución parcial ya no puede llevar a una solución válida, retrocede (backtrack) y prueba otro camino. Es como resolver un laberinto: avanzas por un pasillo, si llegas a un callejón sin salida, retrocedes y pruebas el otro pasillo. Sin poda sería fuerza bruta; con buena poda puede ser mucho más eficiente.

El template de backtracking es siempre el mismo: función recursiva con el estado actual, base case cuando la solución está completa, y un loop que prueba cada opción (agregar al estado, llamar recursivamente, quitar del estado).

Los problemas clásicos son: generar todas las permutaciones de un array, generar todos los subconjuntos, resolver Sudoku, N-Queens (colocar N reinas en un tablero sin que se ataquen), y el problema de la suma de subconjuntos. Todos comparten el mismo skeleton de código.

// Patrón general de Backtracking
// function backtrack(estado, opciones) {
//   if (caso_base) { guardar_resultado; return; }
//   for (opcion de opciones) {
//     hacer_eleccion(opcion);
//     backtrack(nuevo_estado, nuevas_opciones);
//     deshacer_eleccion(opcion);  // ← el "back"
//   }
// }

// Generar todas las permutaciones
function permutaciones(nums) {
  const resultado = [];
  
  function backtrack(actual, restantes) {
    if (restantes.length === 0) {
      resultado.push([...actual]);
      return;
    }
    for (let i = 0; i < restantes.length; i++) {
      actual.push(restantes[i]);
      backtrack(actual, restantes.filter((_, j) => j !== i));
      actual.pop(); // Deshacer
    }
  }
  
  backtrack([], nums);
  return resultado;
}

console.log(permutaciones([1,2,3]).length); // 6

// Generar todos los subsets
function subsets(nums) {
  const resultado = [];
  
  function backtrack(inicio, actual) {
    resultado.push([...actual]);
    for (let i = inicio; i < nums.length; i++) {
      actual.push(nums[i]);
      backtrack(i + 1, actual);
      actual.pop();
    }
  }
  
  backtrack(0, []);
  return resultado;
}

// Combinaciones que sumen target (Combination Sum)
function combinationSum(candidatos, objetivo) {
  const resultado = [];
  candidatos.sort((a, b) => a - b);
  
  function backtrack(inicio, actual, suma) {
    if (suma === objetivo) { resultado.push([...actual]); return; }
    if (suma > objetivo) return; // Poda - no seguir
    
    for (let i = inicio; i < candidatos.length; i++) {
      actual.push(candidatos[i]);
      backtrack(i, actual, suma + candidatos[i]); // i (no i+1) = se puede reusar
      actual.pop();
    }
  }
  
  backtrack(0, [], 0);
  return resultado;
}

console.log(combinationSum([2,3,6,7], 7));
// [[2,2,3], [7]]