pruning proof
가지치기는 전제, 잘리는 분기, 반례로 검증한다
조건 하나가 안전하려면 왜 정답 경로를 자르지 않는지 작은 반례 세트로 확인해야 한다.
safe
unsafe
| 조건 | 전제 | 잘리는 분기 | 반례 세트 |
|---|---|---|---|
| 현재 합 > 목표 | 남은 수가 모두 양수 | 더 내려가도 목표를 넘는다. | 음수가 있으면 실패 |
| 현재 합 + 남은 최대 < 목표 | 남은 후보의 최대 합을 안다. | 목표에 도달할 수 없다. | 후보 합 계산 누락 |
| 중복 후보 건너뛰기 | 정렬되어 있고 같은 깊이다. | 같은 순열을 반복하지 않는다. | 다른 깊이 중복 제거 |