백트랙킹

가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

깊이우선탐색(DFS)에서 끝까지 갔을 때 돌아가는 것 → 백트래킹

백트랙킹 알고리즘에서는 해가 있을 가능성이 없을 경우 백트랙킹 활용

합이 6을 넘는 경우 알아보기

{1, 2, 3, 4} 중 2개의 숫자를 뽑아서 합이 6을 초과하는 경우를 알아내는 백트래킹 알고리즘

(뽑는 순서가 다르면 다른 경우의 수로 간주)


처음에 뽑은 숫자가 3 미만이면 백트래킹한다’라는 전략을 사용

→ 특정 조건을 정의하는 것을 유망 함수(Promising Function)를 정의한다라고 표현함

1과 2는 유망 함수를 통과하지 못하여 백트래킹