백트래킹 후보 복원

상태 최소화

path, used, sum처럼 다음 단계 판단에 필요한 값만 들고 간다.

남은 후보로도 목표에 도달할 수 없거나 이미 조건을 넘었을 때만 안전하게 중단한다.

push와 pop, used=true와 false가 같은 스코프 안에서 짝을 이뤄야 한다.

Permutation

순서 있는 선택 used 배열로 이미 고른 원소를 막는다.

중복 값 처리 규칙이 필요하다.

Combination

순서 없는 선택 start index를 넘겨 이전 후보를 다시 고르지 않는다.

정렬 후 중복 skip이 자주 쓰인다.

Pruning

안전한 배제 버린 가지에 답이 없다는 근거가 있어야 한다.

감으로 자르면 오답이 된다.

Restore

상태 원복 재귀 호출 뒤 공유 상태를 이전 값으로 되돌린다.

예외나 return 경로도 본다.

중복 같은 값이 여러 개 있을 때 같은 조합을 여러 번 만들지 않는가.

원복 모든 선택 뒤에 path와 used가 정확히 되돌아오는가.

가지치기 잘라낸 가지에 가능한 답이 없다는 조건을 증명할 수 있는가.

path.push_back(x);
used[i] = true;
backtrack(depth + 1);
used[i] = false;
path.pop_back();