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