외판원 순회 문제도 해밀턴 순환 회로긴 한데

정올 기출문제를 보면 마을의 개수 N<=12

외판원 순회 문제는 N<=16

이렇게 사이즈가 나와있습니다.

정올 기출 풀이를 보면 백트래킹으로 푸는 풀이도 존재하구요.

근데 해밀턴 순환 회로 문제를 백트래킹으로 풀게 되면 O(N!) 으로 최악의 경우 12! = 479,001,600 이렇게 나오는데

이걸 어떻게 백트래킹으로 풀 생각을 할 수 있는건가요?.... 정답이 나오니까 그렇게 풀이방식이 나왔겠지만

풀기 전에 생각해보면 단순 백트래킹으론 못풀겠다.

외판원 순회 문제 풀듯이 풀어야겠다. ex) 비트마스킹, DP

이렇게 생각이 나가야 되는거 아닌가요?

알고리즘 공부한지 얼마 안돼서 둘의 차이가 뭐길래, 풀이방식이 이렇게 극명하게 달라질 수 있는지 모르겠습니다...

제가 보기엔 정올 기출 해밀턴 순환회로 문제도 단순 백트래킹으로 풀면 시간초과 뜰 것  같은데 말이죠..