El árbol de decisión
Paso 1 de 8
Todo problema de backtracking es este árbol. La raíz es el camino vacío; cada nivel elige una letra más.
La idea
El backtracking es una búsqueda en profundidad (DFS) sobre un árbol que nunca construyes. Cada nodo es una respuesta parcial, cada arista es una elección y cada hoja es un candidato terminado.
El bucle siempre son los mismos tres movimientos: hacer push de una elección al camino, hacer la llamada recursiva para extenderlo y luego hacer pop. Ese pop es todo el truco: restaura el camino para que la siguiente opción empiece exactamente desde el mismo estado, y por eso una sola lista sirve para toda la búsqueda.
Ejemplo del mundo real
Probar las llaves de un llavero sin etiquetas en un edificio con varias puertas cerradas. Tomas una llave, avanzas más adentro y, cuando una puerta no abre, devuelves esa llave al llavero antes de probar la siguiente; si no, el llavero queda mal para todos los intentos que siguen.
El código
Te toca
¿Qué imprime esto?
out = []
walk(["a", "b"], [], out)
print(out)Mini quiz
1 / 3