백트래킹은 부분 해를 확장하다가 조건을 만족할 수 없으면 이전 상태로 돌아가 다른 선택을 탐색하는 방법이다.
원리
선택, 재귀 탐색, 선택 취소의 순서로 상태를 관리한다. 가지치기는 해당 분기에서 유효한 해가 나올 수 없다는 근거가 있어야 한다.
예시
체스판에 퀸을 한 행씩 놓으며 이미 놓인 퀸과 같은 열이나 대각선이면 그 선택을 중단한다. 모든 배치를 끝까지 만들고 검사할 필요가 줄어든다.
주의할 점
가지치기가 있어도 최악의 탐색 공간은 클 수 있다. 공유 배열이나 집합을 수정했다면 돌아올 때 복원해야 다른 분기의 결과가 오염되지 않는다.