레이팅 미적용설명
서로 다른 위치에 놓인 양의 정수 \(N\)개가 주어진다. 이 중에서 일부(공집합 제외)를 골라 그 합이 정확히 \(S\)가 되도록 하려 한다.
합이 \(S\)가 되는 서로 다른 선택 방법의 수를 출력하여라. 위치로 원소를 구분하므로 값이 같아도 다른 위치의 원소는 다른 것으로 센다.
제약
\(1 \le N \le 30\), \(1 \le S \le 10^9\), 각 원소는 \(1\) 이상 \(10^8\) 이하이다.
입력 형식
첫째 줄에 원소의 개수 \(N\)과 목표 합 \(S\)가 주어진다. 둘째 줄에 \(N\)개의 양의 정수가 공백으로 구분되어 주어진다.
출력 형식
합이 정확히 \(S\)가 되는 선택 방법의 수를 출력한다.
예제 1
입력
4 5
1 2 3 4
출력
2설명
원소 \(1,2,3,4\)에서 합이 \(5\)가 되는 부분집합은 \(\{1,4\}\)와 \(\{2,3\}\)이다.
예제 2
입력
3 10
1 2 3
출력
0설명
어떤 부분집합으로도 합 \(10\)을 만들 수 없다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
riseoj 작성
출처 Original
태그