Wrong Code

I was just doing the problem “Number Of Subsets With A Given Sum” but in my code I am getting an integer overflow, can anyone explain why?

using namespace std;

int NumberOfSubsetsWithAGivenSum(int arr[], int size, int target){
    int dp[size+1][target+1];
    for(int i=0; i<size+1; i++){
        dp[i][0]=1;
    }

  for(int j=1; j<target+1; j++){
      dp[0][j]=0;
  }

  for(int i=0; i<size+1; i++){
    for(int j=0; j<target+1; j++){
      if(arr[i-1]<=j){
          dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i-1]];
      } else{
          dp[i][j]=dp[i-1][j];
      }
    }
  }

  return dp[size][target];
     
}

int main(){
  int size;
  cin>> size;

  int arr[size];
  for(int i=0; i<size; i++){
      cin>> arr[i];
  }

  int target;
  cin>> target;

  cout << NumberOfSubsetsWithAGivenSum(arr, size, target) << endl;
  return 0;
} ```

You are initiating the nested for loops from i=0 & j = 0, whereas you have statements like

dp[i][j]=dp[i-1][j];

So it seems like your code is picking up a garbage value instead of overflowing.

Oh right. Thanks, I just forgot that I need to initiate the loops from i=1 and j=1.

1 Like