call cycle
백트래킹의 한 사이클은 선택, 표시, 재귀, 복원이다
상태를 바꾸고 내려간 뒤 같은 변경을 되돌려야 다음 후보가 깨끗한 상태에서 시작한다.
choose
mark
recurse
undo
1
후보 선택
현재 깊이에서 시도할 후보를 하나 고른다.
2
상태 표시
path, used, 합 같은 상태를 갱신한다.
3
재귀 호출
다음 깊이에서 같은 규칙을 반복한다.
4
상태 복원
방금 바꾼 값을 되돌려 다음 후보에 영향을 주지 않는다.
5
다음 후보
복원된 상태에서 같은 깊이의 다음 후보를 본다.
| 유형 | 핵심 차이 |
|---|---|
| 순열 | 사용 여부를 표시해 같은 원소를 다시 쓰지 않는다. |
| 조합 | 시작 인덱스를 넘겨 중복 순서를 제거한다. |
| 가지치기 | 정답 가능성이 사라진 분기만 중단한다. |