선택의 가지를 탐색
여러 선택을 순서대로 정하는 문제를 탐색 트리로 볼 수 있다. 한 선택을 추가한 뒤 그 상태에서 남은 결정을 진행하고, 끝나면 다른 선택을 시험한다. 깊이 우선 방식의 재귀 구현이 흔하다.
중간에 실패를 확인
서로 다른 숫자 두 개를 순서 있게 고르는 과정에서 첫 숫자를 2로 골랐다면 둘째 숫자로 2를 고르는 가지는 제외할 수 있다. 완성한 뒤에만 중복을 검사하는 것보다 일찍 불가능한 후보를 끊는 방식이다.
상태를 되돌리기
공유 배열이나 집합을 수정하며 탐색한다면 한 가지의 탐색이 끝난 뒤 다음 가지에 영향을 남기지 않도록 복원해야 한다. 상태를 복사해 전달하는 방식에서는 복사 비용과 변경 범위도 살핀다.
해의 개수와 종료
해 하나만 필요하면 찾은 뒤 종료할 수 있지만 모든 해가 필요하면 남은 가지도 검토해야 한다. 가지치기를 하더라도 최악의 경우 많은 후보를 탐색할 수 있으므로 언제나 다항 시간에 끝나는 기법은 아니다.
관련 문서
재귀 / 깊이 우선 탐색 / 트리 (그래프 이론) / 알고리즘 / 순열 / 집합 / 시간 복잡도 / 탐욕 알고리즘