백트래킹

• 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘
• 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 (모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것)
• 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음
  만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감
• 재귀로 푸니까 스택 메모리 제한 확인해야됨
• 시간복잡도 O(N!) 개 오 래 걸 림 (N이 클 경우 백트래킹을 적용하면 시간초과 남)
  12! = 479001600 = 4*10^8

기본 틀

void backtracking(int cnt, int idx) {
    if (cnt == m) {
        //조건 만족시 해야될 일 적음
        return;
    }
    for (int i = idx; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true; //상태변화
            backtracking(cnt + 1, i); 
            visited[i] = false; //원상복구
        }
    }
}

백트래킹 코드는 이 틀 내에서 문제에 따라 적절히 응용해야함
인덱스 설정이나 탈출 조건은 문제에 따라 바꿔주면 되고
상태변화 & 원상복구가 중요함 원래대로 복구하는거 빼먹지 않도록 주의

레퍼런스