BACKTRACKING

가지치기는 탐색을 줄이되 정답 경로는 절대 자르면 안 된다

재귀 문법보다 먼저 상태, 후보, 중단 조건의 안전성을 문장으로 고정해야 한다.

상태 표현

현재까지 선택한 값과 제약 사용 여부를 다음 후보 생성에 필요한 만큼만 저장한다.

가지치기 조건

부분해가 제약을 위반했거나 남은 후보로 목표에 닿을 수 없을 때만 중단한다.

상태 복원

재귀 호출 전 바꾼 선택 정보를 호출 후 되돌려 형제 분기를 독립적으로 유지한다.

안전한 예: 모든 수가 양수일 때 현재 합이 목표를 넘으면 하위 탐색을 중단한다.

위험한 예: 전제가 없는 과한 조건은 정답 조합을 포함한 분기까지 잘라낼 수 있다.