# Untitled

unknown
c_cpp
7 months ago
1.5 kB
3
Indexable
Never
```//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution {
public:
int mod=1e9+7;
int SubSetSum(vector<int>&arr,int sum){
int n=arr.size();
int dp[n+1][sum+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++){
if(i==0){
dp[i][j]=0;
}
if(j==0){
dp[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=sum;j++){
if(arr[i-1]<=j){
dp[i][j]=(dp[i-1][j] %mod + dp[i-1][j-arr[i-1]] %mod) % mod;
}
else{
dp[i][j]=dp[i-1][j] %mod;
}
}
}
return dp[n][sum] % mod;
}
int countPartitions(int n, int d, vector<int>& arr) {
int sum=0;
for(int i=0;i<n;i++){
sum+=arr[i];
}
if((sum+d)%2!=0){
return 0;
}
else{
int new_sum=((d+sum)/2);
return SubSetSum(arr,new_sum) % mod;
}

}
};

//{ Driver Code Starts.
int main() {
int t;
cin >> t;
while (t--) {
int n, d;
cin >> n >> d;
vector<int> arr;

for (int i = 0; i < n; ++i) {
int x;
cin >> x;
arr.push_back(x);
}

Solution obj;
cout << obj.countPartitions(n, d, arr) << "\n";
}
return 0;
}
// } Driver Code Ends```