백트래킹, 가지치기 구현 템플릿

1. backtracking

void backtrack(List<Integer> path) {
    if (isFinished(path)) {  // 종료 조건 만족
        answers.add(new ArrayList<>(path));  // 현재 경로 저장
        return;
    }

    for (int choice : getChoices(path)) {  // 가능한 모든 선택
        path.add(choice);  // 현재 선택 추가
        backtrack(path);   // 다음 단계 탐색
        path.remove(path.size() - 1);  // 원래 상태로 되돌리기 (Backtracking)
    }
}

2. backtracking + pruning

void backtrack(List<Integer> path) {
    if (isFinished(path)) {  // 종료 조건 만족
        answers.add(new ArrayList<>(path));  // 현재 경로 저장
        return;
    }

    for (int choice : getChoices(path)) {  // 가능한 모든 선택
		    if (!isValid(choice)) // 가지치기
		        continue;

        path.add(choice);  // 현재 선택 추가
        backtrack(path);   // 다음 단계 탐색
        path.remove(path.size() - 1);  // 원래 상태로 되돌리기 (Backtracking)
    }
}