sum of subsets problem이란 n개의 양의 정수(w1,w2,...,wn)와, 임의의 양의 정수 W가 있을 때, 다 합쳐서 W가 되는 모든 부분집합을 구하는 문제이다. 이 문제를 백트래킹을 사용하여 해결할 수 있다. 먼저 backtracking 문제를 풀기위해서는 상태공간트리의 구조와, 유망함수를 구축해야한다. sum of subsets 문제의 경우 상태공간트리의 구조와 유망함수는 다음과 같다. ① 상태공간트리의 구조 오름차순으로 level을 결정 ② 유망함수(promising function) weight + wi+1이 W보다 큰가? ≫ non-promising weight + total이 W보다 작은가? ≫ non-promising 양의 정수들을 오름차순으로 정렬하고, 작은 것 부터 즉 ..