완전 검색을 적용하는 데는 크게 두 가지 문제가 있다. 첫째, 모든 가능한 풀이 후보를 생성하는 과정이다. 문제에 따라 풀이 후보가 잘 짜인 집합으로 만들어질 수도 있다. 예를 들어 (위에 있는 마방진 예제에서처럼) 3 × 3 표를 1부터 9까지의 정수로 채우는 풀이 후보는 이 아홉 개 정수의 순열(permutation)로 구할 수 있다. 하지만 풀이 후보가 그렇게 규칙적인 구조를 가진 집합으로 만들어지지 않는다는 문제점도 많다. 둘째, 더 근본적인 문제점은 생성해 처리해야 할 풀이 후보의 수다. 일반적으로 풀이 후보의 집합 크기는 문제의 크기에 대해 최소한 지수함수적으로 커진다. 따라서 완전 검색은 그런 문제의 매우 작은 인스턴스에 관해서만 쓸 수 있다.

역추적(backtracking)은 완전 검색의 주먹구구식 접근법에 비하면 상당히 발전된 방식이다. 역추적은 불필요한 후보는 생성하지 않으면서 적절한 풀이 후보를 생성하도록 해주는 편리한 방법이다. 기본 개념은 풀이를 한 번에 하나씩 구축하면서 부분적으로 구축된 후보를 다음과 같은 식으로 평가하는 것이다. 부분적으로 구축된 풀이가 문제의 제약 조건을 위반하지 않으면서 앞으로 나갈 수 있다면 우선 다음 구성 요소를 위한 첫 번째 합당한 옵션을 취하는 것부터 시작한다. 다음 구성 요소에 맞는 합당한 옵션이 없다면 그 뒤로 이어지는 나머지 구성 요소는 따져볼 필요도 없다. 이런 경우, 부분적으로 구축된 풀이의 마지막 구성 요소를 대체할 만한 다른 옵션으로 역추적해 돌아간다.