합이 S인 부분집합 수
실버 III의견: 0
서로 다른 위치에 놓인 양의 정수 \(N\)개가 주어진다. 이 중에서 일부(공집합 제외)를 골라 그 합이 정확히 \(S\)가 되도록 하려 한다.
합이 \(S\)가 되는 서로 다른 선택 방법의 수를 출력하여라. 위치로 원소를 구분하므로 값이 같아도 다른 위치의 원소는 다른 것으로 센다.
\(1 \le N \le 30\), \(1 \le S \le 10^9\), 각 원소는 \(1\) 이상 \(10^8\) 이하이다.
첫째 줄에 원소의 개수 \(N\)과 목표 합 \(S\)가 주어진다. 둘째 줄에 \(N\)개의 양의 정수가 공백으로 구분되어 주어진다.
합이 정확히 \(S\)가 되는 선택 방법의 수를 출력한다.
4 5
1 2 3 4
2원소 \(1,2,3,4\)에서 합이 \(5\)가 되는 부분집합은 \(\{1,4\}\)와 \(\{2,3\}\)이다.
3 10
1 2 3
0어떤 부분집합으로도 합 \(10\)을 만들 수 없다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
합이 S인 부분집합 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
합이 S인 부분집합 수