# 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