Advertisement
Oppenheimer

Count no of subsets with given sum

Aug 14th, 2022 (edited)
30
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. //count the number of subsets with given sum
  2. // correct only if each values[i] is greater than 0
  3. int solve(vector<int> value , int target){
  4.     int  n = value.size();
  5.     int sum=0;
  6.     for(int a=0;a<n;a++)sum+=value[a];
  7.     if(target > sum) return 0;
  8.     vector<vector<int>> dp (n+1 ,vector<int>(sum+1,0));
  9.     // a represents the ath element .. b represents the knapsack present
  10.    
  11.     for(int a=0;a<=n;a++)dp[a][0] = 1;// sum 0 is possible even if do not select anything
  12.    
  13.     for(int a=1;a<=n;a++){
  14.         for(int b=1;b<=sum;b++){
  15.             if(value[a-1]<=b){
  16.             dp[a][b] = dp[a-1][b-value[a-1]] + dp[a-1][b]; //either i choose the ath element or not
  17.             }else{
  18.             dp[a][b] = dp[a-1][b]; // cant choose the ath element becuase its weight is more
  19.             }
  20.         }
  21.     }
  22.     return dp[n][target];
  23.  
  24. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement