current > target
모든 수가 양수이면 더 내려가도 합은 줄지 않으므로 분기를 닫아도 된다.
가지치기 검증
빠른 조건보다 중요한 것은 정답 경로를 절대 자르지 않는다는 설명입니다.
부분집합 합 기준 입력
nums
[7, 3, 2, 5, 8]
target
14
answer
7 + 5 + 2
남은 합 부족
현재 합에 남은 수를 모두 더해도 목표에 못 미치면 정답 가능성이 없다.
전제 없는 초과 컷
음수나 0이 섞이면 초과한 합이 뒤에서 다시 내려갈 수 있어 정답을 잃는다.
전제
양수 배열, 한 해만 필요한지, 모든 해를 모아야 하는지 먼저 적는다.
전제가 바뀌면 같은 조건도 오답이 될 수 있다.
잘리는 분기
idx, current, 남은 후보를 함께 써서 실제로
버리는 노드를 설명한다.
설명할 수 없는 컷은 제거하고 로그로 비교한다.
복원
방문 배열, 열, 대각선, 현재 합은 재귀 호출 후 반드시 원래대로 돌린다.
형제 분기가 오염되면 가지치기 조건이 맞아도 결과가 틀린다.