문제 설명
\(N\)정수로 이루어진 집합이 주어졌을 때, 이 집합으로 만들 수 있는 부분 집합 중 부분 집합의 원소의 총 합이 \(S\)인 부분 집합의 개수를 구하여보자.
예를 들어 \(5\)개의 원소를 가진 집합\((N=5)\)이 다음과 같이 주어졌을 때,
예를 들어 \(5\)개의 원소를 가진 집합\((N=5)\)이 다음과 같이 주어졌을 때,
\(\{-7,-3,-2,5,8\}\)
부분 집합의 합\((S)\)이 \(0\)인 경우는 \(1\)가지만 존재 한다.
\(\{-3, -2, 5\} : -3 + -2 + 5 = 0\)
입력 설명
첫 번째 줄에 배열의 크기\(N(1 \le N \le 20)\)과 부분 집합의 합\(S(0 \le S \le 1000)\)가 공백으로 구분되어 입력된다.
둘째 줄에 \(N\)개의 정수\((A_i)\)가 주어진다. \((-1000 \le A_i \le 1000)\)
둘째 줄에 \(N\)개의 정수\((A_i)\)가 주어진다. \((-1000 \le A_i \le 1000)\)
출력 설명
부분 집합의 합이 \(S\)인 부분 집합의 개수를 출력한다.
입력 예시 Copy
5 0
-7 -3 -2 5 8
출력 예시 Copy
1