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];
}