백트래킹

답이 될 수 있는 경우를 하나씩 골라 나가다가, 이 길로는 답이 안 된다는 것이 보이면 바로 앞 선택으로 되돌아가(back) 다른 것을 고르는 방법이다. 모든 경우를 끝까지 만들어 보는 것보다, 안 될 길을 일찍 끊어서 덜 본다. 보통 [재귀](/term/recursion)로 구현한다.