백트래킹(Backtracking)은 문제 해결을 위한 알고리즘 설계 기법 중 하나로, 가능한 해를 찾기 위해 다양한 경로를 탐색하는 방법이다. 이 기법은 주로 조합 최적화 문제, 그래프 이론, 퍼즐 문제 등에 응용된다.

백트래킹 알고리즘의 기본 원리는 다음과 같다. 문제의 해를 구성하는 각 단계를 차례로 선택하고, 선택한 단계가 유효한지를 평가한다. 만약 현재 단계에서 선택한 해가 유효하지 않다면, 이전 단계로 돌아가서 다른 선택지를 고려하는 과정을 반복한다. 이때 '되돌아가기(backtrack)'라는 절차를 통해 모든 가능한 해결책을 탐색하며, 최종적으로는 조건을 만족하는 해를 찾아낸다.

백트래킹은 깊이 우선 탐색(Depth-First Search) 방식으로 구현되는 경우가 많다. 이를 통해 각 노드에서 가능한 모든 경로를 탐색하게 되며, 특정 조건(예: 선택한 해의 유효성)을 만족하지 않을 경우, 즉시 이전 단계로 돌아가 다른 경로를 시도할 수 있다. 이러한 방식은 전체 탐색 공간을 효율적으로 줄일 수 있으며, 최적의 해를 찾기 위한 다양한 접근법 중 하나로 사용된다.

백트래킹의 대표적인 예로는 퍼즐 문제, N-Queens 문제, 부분 집합 생성, 미로 탐색 등이 있다. 이러한 문제들은 대체로 결정적인 해가 존재하지 않거나, 최적의 해를 찾기 위한 다양한 경로가 필요하기 때문에 백트래킹을 통해 해결할 수 있다.

이 알고리즘은 단순하면서도 강력한 문제 해결 방법으로, 많은 컴퓨터 과학 및 프로그래밍 문제에서 기본적인 접근 방식으로 자리 잡고 있다. 그러나 백트래킹은 경우에 따라 계산 복잡성이 높아질 수 있기 때문에, 최적화나 가지치기 기법과 함께 사용되는 경우가 많다.