[알고리즘] Backtracking - Sum of Subsets

Backtracking은 DFS와 같은 방식으로 트리를 탐색하는 방법 중 하나다. 탐색을 진행하다가 더 갈 수 없으면 다시 이전 노드로 돌아와 탐색하는 방법이다. Sum of Subsets 문제도 backtracking으로 풀 수 있는 문제 중 하나다.

 

Sum of Subsets은 집합 wi의 부분 집합 중 그 합이 W와 같은 부분 집합들을 찾는 문제다. 예를 들어서, 𝑛 = 5, 𝑊 = 21, and 𝑤𝑖 = [5, 6, 10, 11, 16]이 주어졌다고 하자. 그러면 21이 될 수 있는 조합은 {5, 6, 10}, {5, 16}, {10, 11}이다. 이렇게 푸는 것을 상태공간트리를 만들어서 풀어보자.

 

왼쪽은 wi를 포함시키는 것이고 오른쪽은 wi를 포함하지 않을 때의 값이다. weight가 W와 같다면 pruning을 멈추고, 그게 아니라면 탐색할 수 있다. 그러나, 이때 해당 노드가 promising인지 알아야 한다. 정확하게 알 수 있는 방법은 현재까지의 weight와 해당 노드 다음 값인 wi+1을 더했을 때 W보다 크다면, non-promising으로 판단하고 더이상 탐색하지 않는다.

 

따라서 상태노드트리의 전체 노드 개수는 23개이고 원래 트리의 노드 개수는 63개이다.