Backtracking

Backtracking 이란?
 어떤 문제를 풀 수 있는 여러개의 solution 중에서 특정 조건을 충족시키는 모든 solution을 찾는 알고리즘이다

 예로써, 1000원을 500원, 100원, 50원, 10원으로 낼 수 있는 방법은 500원 2개, 100원 10개, 500원 1개와 100원 5개를 내는 등 많은 방법이 존재한다. 이러한 방법들 중에서 동전 2개만 내라는 특정 조건을 충족시키는 해는 500원 2개를 내는 것이다. 이처럼 특정 조건을 충족시키는 solution 모두 찾는 알고리즘이다.