재귀적으로 전부 다 해보는데 조건에 맞지 않으면 가지치기로 쳐내고 유의미한 곳만 탐색한다..!
탐색을 하는데 (dfs와 탐색법이 비슷하다) 만약 조건에 맞지 않는다면 중지하고 이전으로 돌아가서 원하는 조건을 찾는 방식!
예를들어
겹치지 않는 홀수만 가지고 오름차순 세자리를 만드는 문제라 하면? ( 135, 195 등등)
첫번째 자리 1부터 9까지 하나씩 넣어봄
첫번째로 1이 왔다고 치자
1 _ _
두번째자리 아무거나 넣어봄
1 2 _
여기서 2는 홀수가 아니기 때문에 종료하고 다시 1 _ _ 로 돌아가는 것이 백트래킹
( 1 2 3, 1 2 4, 1 2 5 등등은 시도해볼 필요도 없다 , 2가 짝수이므로)
다시 1 _ _ 로 돌아가서 이번에는 3을 넣고 1 3 _ 로 돌려서 조건에 맞는걸 계속해서 찾아간다
dfs와 다른 점은 dfs는 모든 경우를 탐색하므로 1 2 3까지 간 후에 조건에 안맞음을 확인하는데,
백트래킹 이용 시 1 2 에서부터 자르므로 탐색 횟수가 줄어들게 된다