백트래킹

개념

 - 모든 경우의수를 확인해야 할때

  - for로는 확인 불가한 경우( 깊이가 달라질때 )

 

순열 : M개의 숫자 중 N개를 뽑을때 순서에 상관하여 뽑는 방식

 

3개에서 2개를 뽑는다면 for로 확인하면 된다.

 

백트래킹은? M, N이 주어졌을 경우!

재귀함수로 구현을 한다. 깊이를 마음대로 설정할 수 있게된다.

 

중요한 것은 특정 상태를 제외한다는 것이다.

 

백트래킹은 현재 상태에서 다음 상태로 나아갈 수 있는 모든 경우를 찾되, 그 중

유망하지 않다면 현재에서 더 이상 나아가지 않고 이전의 상태로 돌아가 다음 상태를 검사한다.

 

더이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기라고 한다.