Doubt (Stuck for an hour) Help needed

I have written the following dp code for finding the number of subsets for a given sum. But it doesn’t work for the input: {1, 2, 3, 3} and W =6.
Can someone help?

int subsx(int arr[], int n, int W)
{ 
// arr = {1,2,3,3}, n = 4, W = 6
// Expected o/p = 3, and the o/p it's showing = 1 

int dp[n + 1][W + 1];
for(int i = 0 ; i < (n + 1); i++) {
for(int j = 0; j < (W + 1); j++) {
if (i == 0 or j == 0) 
{
dp[i][j] = 0 ;
  if (j == 0) 
  { dp[i][j] = 1; }
}
else {
	if (arr[i] > W) {
    dp[i][j] = dp[i - 1][j];
         }
			
    else {
	dp[i][j] = ((dp[i - 1][j]) + (dp[i - 1][j - arr[i - 1]]));
	     }
	}
}
}
return dp[n][W];
}

In condition if(arr[i]>w) instead you should check if(arr[i-1]>j).
I think that is creating error.

1 Like

Thank you @shaurya_upd. You are right.

1 Like

Don’t put unnecessary if-else statements, it only makes your code prone to bugs, in fact you don’t even need a 2-D array.

CODE
#include "bits/stdc++.h"
using namespace std ;
int main(){	
	int n,w  ;
	cin >>n >>w ;
	vector<int>a(n),dp(w+1) ;
	dp[0]=1 ;
	for(int &x:a){
		cin >>x  ;
		for(int j=w;j>=x;--j)
			dp[j]+=dp[j-x] ;
	}
	cout<<dp[w] ; 
}
1 Like

Thank you for the advice. I’ll take care.

1 Like