백트래킹

해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법

가지치기라고도 부른다

불필요한 부분을 쳐내기 때문에 DFS보다 효율적이다. 하지만 N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸린다.

주로 깊이 우선 탐색(DFS) 등으로 모든 경우의 수를 탐색하는 과정에서 답이 절대 될 수없는 상황을 정의하고 탐색을 중지시키는 방식으로 구현할 수 있다.