Backtracking rakentaa kandidaattiratkaisuja vähitellen ja hylkää (perääntyy) osittaisen kandidaatin heti, kun se ei voi johtaa kelvolliseen ratkaisuun. Se tutkii ratkaisuavaruutta systemaattisesti DFS:n kautta ja karsii umpikujat.
Idea
Valitse -> tutki -> peru valinta. Yritä vaihtoehtoa, rekursio; jos epäonnistuu, peru ja yritä seuraavaa.
Esimerkki: kaikki permutaatiot
():
result = []
():
remaining:
result.append(path[:])
i ((remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+:])
path.pop()
backtrack([], nums)
result
permutations([, , ])
