Backtracking costruisce soluzioni candidate in modo incrementale e abbandona (backtrack) un candidato parziale non appena non può portare a una soluzione valida. Esplora sistematicamente lo spazio delle soluzioni tramite DFS, potando i rami senza soluzione.
L'idea
Scegli -> esplora -> annulla la scelta. Prova un'opzione, ricorri; se fallisce, annulla e prova la successiva.
Esempio: tutte le permutazioni
():
result = []
():
remaining:
result.append(path[:])
i ((remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+:])
path.pop()
backtrack([], nums)
result
permutations([, , ])
