Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Solution:
#include<iostream>
#include<stdio.h>
using namespace std;
bool isSubsetSum(int set[], int n, int sum)
{
bool subset[sum+1][n+1];
// If sum is 0, then answer is true
for (int i = 0; i <= n; i++)
subset[0][i] = true;
// If sum is not 0 and set is empty, then answer is false
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
for (int i = 1; i <= sum; i++)
{
for (int j = 1; j <= n; j++)
{
subset[i][j] = subset[i][j-1];
if (i >= set[j-1])
subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
}
}
return subset[sum][n];
}
int main()
{
int T = 0 ;
cin>>T;
int *a;
int n = 0;
int sum = 0 ;
for(int t = 0 ; t < T ; t++)
{
cin>>n;
a = new int[n];
for(int i = 0 ; i < n ; i++)
{
cin>>a[i];
}
cin>>sum;
if (isSubsetSum(a , n , sum ) == true)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
delete []a;
}
return 0;
}
No comments:
Post a Comment