Data Structure & Algorithms
Backtracking para subsets, combinations y permutations, con restauración de estado, manejo de duplicados, pruning y análisis de salida exponencial.
Backtracking explora un árbol de decisiones. En cada nodo:
choose → explore → unchooseNo es simplemente “usar recursión”. La idea central es construir soluciones incrementales y restaurar el estado para compartir una misma estructura entre ramas.
Para elegir subconjuntos de [A, B]:
graph TD
R[ ] --> A1[incluir A]
R --> A0[omitir A]
A1 --> AB[incluir B: A,B]
A1 --> A[in omitir B: A]
A0 --> B[incluir B: B]
A0 --> E[omitir B: ]Cada raíz-hoja representa una solución. El branching factor y la profundidad determinan la cantidad de estados explorados.
function backtrack<State, Choice>(state: State, choices: Choice[]): void {
if (isComplete(state)) {
record(state);
return;
}
for (const choice of choices) {
if (!isValid(state, choice)) continue;
apply(state, choice);
backtrack(state, nextChoices(state));
undo(state, choice);
}
}Las funciones concretas dependen del problema. undo debe restaurar exactamente el estado anterior.
Cada elemento tiene dos decisiones: incluir u omitir. Hay 2^n subconjuntos.
Una forma compacta agrega el estado actual en cada nodo y elige el siguiente índice.
function subsets<T>(values: readonly T[]): T[][] {
const result: T[][] = [];
const current: T[] = [];
function visit(start: number): void {
result.push([...current]);
for (let index = start; index < values.length; index += 1) {
current.push(values[index]);
visit(index + 1);
current.pop();
}
}
visit(0);
return result;
}current contiene un subconjunto cuyos índices son estrictamente crecientes y todos son menores que start para la próxima elección. Por eso no genera el mismo conjunto en órdenes diferentes.
Hay 2^n resultados y copiar cada uno cuesta hasta O(n):
O(n · 2^n) contando la materialización;O(n);O(n · 2^n) en el peor caso.No puedes generar explícitamente todos los subconjuntos en tiempo polinomial porque la salida ya es exponencial.
Para elegir exactamente k elementos, el estado incluye cuántos faltan.
function combinations<T>(values: readonly T[], k: number): T[][] {
if (k < 0 || k > values.length) return [];
const result: T[][] = [];
const current: T[] = [];
function visit(start: number): void {
if (current.length === k) {
result.push([...current]);
return;
}
const remainingNeeded = k - current.length;
const lastStart = values.length - remainingNeeded;
for (let index = start; index <= lastStart; index += 1) {
current.push(values[index]);
visit(index + 1);
current.pop();
}
}
visit(0);
return result;
}lastStart es pruning: si quedan menos elementos que elecciones necesarias, esa rama no puede completar una combinación.
La cantidad de resultados es C(n, k). El tiempo al materializarlos es al menos proporcional a k · C(n, k).
En una permutación el orden importa. Cada nivel elige un elemento todavía no usado.
function permutations<T>(values: readonly T[]): T[][] {
const result: T[][] = [];
const current: T[] = [];
const used = Array(values.length).fill(false);
function visit(): void {
if (current.length === values.length) {
result.push([...current]);
return;
}
for (let index = 0; index < values.length; index += 1) {
if (used[index]) continue;
used[index] = true;
current.push(values[index]);
visit();
current.pop();
used[index] = false;
}
}
visit();
return result;
}Hay n! permutaciones. Copiarlas cuesta O(n · n!).
Con entrada [1, 1, 2], usar índices distintos puede producir resultados de valores repetidos.
Una estrategia:
function uniquePermutations(values: readonly number[]): number[][] {
const sorted = [...values].sort((a, b) => a - b);
const result: number[][] = [];
const current: number[] = [];
const used = Array(sorted.length).fill(false);
function visit(): void {
if (current.length === sorted.length) {
result.push([...current]);
return;
}
for (let index = 0; index < sorted.length; index += 1) {
if (used[index]) continue;
if (
index > 0 &&
sorted[index] === sorted[index - 1] &&
!used[index - 1]
) {
continue;
}
used[index] = true;
current.push(sorted[index]);
visit();
current.pop();
used[index] = false;
}
}
visit();
return result;
}La condición evita elegir el segundo valor idéntico como representante de una posición antes que el primero dentro del mismo nivel.
Pruning corta una rama cuando puedes demostrar que no contiene soluciones válidas o no puede mejorar la mejor solución conocida.
Tipos frecuentes:
Una poda incorrecta elimina soluciones reales. Debe justificarse con una propiedad, no con intuición.
function combinationSum(
candidates: readonly number[],
target: number,
): number[][] {
const sorted = [...new Set(candidates)]
.filter((value) => value > 0)
.sort((a, b) => a - b);
const result: number[][] = [];
const current: number[] = [];
function visit(start: number, remaining: number): void {
if (remaining === 0) {
result.push([...current]);
return;
}
for (let index = start; index < sorted.length; index += 1) {
const value = sorted[index];
if (value > remaining) break;
current.push(value);
visit(index, remaining - value);
current.pop();
}
}
visit(0, target);
return result;
}El break solo es seguro porque todos los candidatos son positivos y están ordenados. Con negativos, un valor mayor que remaining podría compensarse después.
Dos estilos:
push → recurse → popvisit([...current, choice]);La complejidad asintótica de la enumeración sigue dominada por el número de soluciones, pero las constantes cambian.
Si solo necesitas saber si existe una solución, devuelve en cuanto encuentres una. No materialices todas.
function existsPath(...): boolean {
// Stop at the first valid leaf.
}La peor complejidad puede seguir siendo exponencial, pero el mejor caso y la memoria de salida mejoran considerablemente.
Backtracking distingue caminos. DP combina caminos que llegan al mismo estado futuro.
Pregunta:
Si dos historias llegan a la misma información relevante, ¿las decisiones futuras son idénticas?
Si sí, memoization puede evitar repetir el subárbol. Si necesitas enumerar cada solución completa, fusionar estados puede requerir guardar cómo reconstruirlas.
Backtracking suele usar DFS sobre un árbol de decisiones implícito. No todo DFS es backtracking: recorrer un árbol existente sin tomar y deshacer decisiones no necesariamente lo es.
Una estimación general:
O(b^d)b: opciones por estado;d: profundidad máxima.Es una cota aproximada. Restricciones, opciones decrecientes y pruning cambian el número real de nodos.
Incluye además:
O(d);used.k = 0;current sin copiarlo y terminar con referencias al mismo array.Set de valores cuando se necesitan índices duplicados.O(2^n) sin contar copia o tamaño de salida.choose → explore → unchoose conserva el invariante entre ramas.¿Por qué result.push(current) suele ser un bug en una implementación con push y pop?
Porque guarda la misma referencia mutable en todos los resultados. Las modificaciones posteriores cambian lo que ven todas las entradas. Debe guardarse una copia como [...current].