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