vendredi 29 mai 2020

Segmentation fault in dynamic programming

I read that Segmentation fault is a specific kind of error caused by accessing memory that “does not belong to you". I can't figure out which part of this code is causing that error to come up.

What is the error in my dynamic programming implementation? I am writing a program to check if an array can be divided into two subsets with equal sum. If the input is {1, 5, 11, 5} the output is YES, because it can be divide like {1, 5, 5} and {11}.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool subsetsum(ll int arr[], ll int sum, ll int n)
{

     int t[n+1][sum+1];
     for(int i = 0; i < n+1; i++)      //INITIALIZATION
     {   for(int j = 0; j < sum+1; j++)
        {
            if(i == 0)
                t[i][j] = false;
            if(j == 0)
                t[i][j] = true;
        }
     }


       for(int i = 1; i < n+1; i++)
    {
        for(int j = 1; j < sum+1; j++)
        {
            if(arr[i-1] <= j)
            {
                t[i][j] = (t[i-1][j-arr[i-1]]) || (t[i-1][j]);
            }
            else
                t[i][j] = t[i-1][j];
        }
    }

    if(t[n][sum])
        return true;
    else
        return false;
 }

 int main()
 {
     ios_base::sync_with_stdio(0);
     cin.tie(0);
     int T;
     cin>>T;
     while(T--)
     {
         ll int n,sum = 0;
         cin>>n;
         ll int arr[n];
         for(int i = 0; i < n; i++)
            cin>>arr[i], sum = sum + arr[i];

         if(sum % 2 != 0)
         {
             cout<<"NO\n";
             continue;
         }

         bool sol = subsetsum(arr,sum/2, n);

         if(sol)
            cout<<"YES\n";
         else
            cout<<"NO\n";
     }

 }


Aucun commentaire:

Enregistrer un commentaire