백트래킹

백트래킹(역 추적)은 일부 계산 문제, 특히 제약 만족 문제에 대한 모든 솔루션을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 가능하지 않다고 결정하는 즉시 후보의 역추적을 포기합니다.

문제)
주어진 리스트 [1,2,3,4]라고 할 때 주어진 리스트에서 2개를 조합하여 만들 수 있는 리스트를 구해보자.

그렇다면 우리는 1을 정해 놓고 올 수 있는 목록들 2,3,4를 하나씩 붙여넣고, 2를 정해서 3,4를 붙여넣고 3을 정해서 4를 붙여 넣어 답을 추려낼 수 있을 것이다.

백트래킹 방식도 마찬가지이다. 말로 설명하기 힘들어 그림으로 표현해 보았다.

즉 모든 경우의 가짓 수를 다 탐색하는 데 만약에 해당 조건을 만족할 경우 역추적을 포기하고 다른 가짓 수를 탐색하는 방식이 바로 백트래킹이다.

이러한 방식의 백트래킹은 재귀로 구현하였을 때 좀 더 효과적으로 구현할 수 있다.