Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // count the number of subsets with given diff ,,
- // s1-s2 = dif and s1+s2 = s ====> s1 = (s+dif)/2
- int solve(vector<int> value , int target){
- int n = value.size();
- int sum=0;
- for(int a=0;a<n;a++)sum+=value[a];
- if(target > sum || (sum+target)%2 == 1) return 0;
- vector<vector<int>> dp (n+1 ,vector<int>(sum+1,0));
- // a represents the ath element .. b represents the knapsack present
- for(int a=0;a<=n;a++)dp[a][0] = 1;// sum 0 is possible even if do not select anything
- for(int a=1;a<=n;a++){
- for(int b=1;b<=sum;b++){
- if(value[a-1]<=b){
- dp[a][b] = dp[a-1][b-value[a-1]] + dp[a-1][b]; //either i choose the ath element or not
- }else{
- dp[a][b] = dp[a-1][b]; // cant choose the ath element becuase its weight is more
- }
- }
- }
- return dp[n][(sum+target)/2];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement