$NP$-$complete$ 문제에 속하는 대표 문제 중 하나인 부분 집합의 합 문제를 간소화하여 풀어보자. 문제는 다음과 같다.

• $n$개의 정수로 이루어진 수열 $a_1, a_2, ... , a_n$이 있다. 고른 수들의 합이 $S$가 되도록 하나 이상의 수를 고를 때, 가능한 경우의 수가 총 몇가지나 있겠는가?

첫째 줄에 $n$과 $S$가 공백으로 구분되어 주어진다. $(1 ≤ n ≤ 20$ $;$ $|S| ≤ 100)$

둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다. $(|a_i| ≤ 100)$