backtracking safety
가지치기는 정답 경로를 보존할 때만 안전하다
분기를 자르기 전에 상태 표현, 자르는 조건, 되돌림 규칙이 정답 가능성을 지우지 않는지 확인한다.
state
cut
restore
상태 표현
현재까지 선택한 값과 다음 후보 생성에 필요한 정보만 남긴다.
가지치기 조건
남은 후보를 모두 써도 정답이 불가능할 때만 분기를 자른다.
상태 복원
재귀 호출 뒤 바꾼 선택 정보를 되돌려 형제 분기가 독립되게 한다.
| 판정 | 조건 | 예시 |
|---|---|---|
| 안전 | 현재 합이 목표를 넘고 모든 수가 양수다. | current > target |
| 위험 | 음수가 섞였는데 합이 크다는 이유만으로 자른다. | 뒤에서 음수로 내려올 수 있다. |