백트래킹

- 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.
- DFS(깊이 우선 탐색) 기반

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.
코딩에서 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 
즉 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 된다. 

예를 들어 A,B,C라는 사람이 각각 순서를 정할때 가능한 모든 경우의 수를 찾는 것으로 첫번째 순서가 A일경우 ,B일경우, C일경우 각각 차례대로 따지는 식이다.