정수 N개에서 부분집합(공집합 포함 안 함)을 골라 합이 S가 되는 개수를 구하세요. N이 커서 전부 탐색하면 느려요.
힌트: 반씩 나눠 각각 모든 합을 구한 뒤 짝을 맞춰 보세요(반씩 탐색).
입력
첫째 줄에 N과 S가 주어져요. (1 ≤ N ≤ 30, |S| ≤ 2,000,000) 둘째 줄에 정수 N개가 주어져요. (|수| ≤ 100,000)
출력
개수를 출력해요.
정수 N개에서 부분집합(공집합 포함 안 함)을 골라 합이 S가 되는 개수를 구하세요. N이 커서 전부 탐색하면 느려요.
힌트: 반씩 나눠 각각 모든 합을 구한 뒤 짝을 맞춰 보세요(반씩 탐색).
첫째 줄에 N과 S가 주어져요. (1 ≤ N ≤ 30, |S| ≤ 2,000,000) 둘째 줄에 정수 N개가 주어져요. (|수| ≤ 100,000)
개수를 출력해요.
5 0 -7 -3 -2 5 8
1
로그인하면 제출할 수 있어요.