Problem 65: Subset Sum Count Modulo Partition
Problem Statement: Given an array of positive integers and an integer S, count the number of subsets that sum exactly to S modulo 10^9+7.
Input
The first line contains n and S. The second line contains n space-separated integers.
Output
Print the number of subsets whose sum equals S modulo 10^9+7.
Examples
Input:
4 5
1 2 3 4
Output:
2
Solution Explanation
Use dynamic programming where dp[i][j] counts the number of ways to achieve sum j using first i elements. Optimize space by using a 1D DP array and iterating backwards.
Solution in C++
#include
#include
using namespace std;
const int MOD = 1000000007;
int main(){
int n, S;
cin >> n >> S;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
vector dp(S + 1, 0);
dp[0] = 1;
for(int num : a){
for(int s = S; s >= num; s--){
dp[s] = (dp[s] + dp[s - num]) % MOD;
}
}
cout << dp[S] << "\n";
return 0;
}