Question

a. Write a function is_subset_sum that takes an integer N and an integer

array A as parameter and returns True if N is a sum of any subset of A and

returns False otherwise. You must use dynamic programming tabulation

method for calculation

b. Write a main function that takes the array A of size s as input from the

console. Then it takes N as input in a loop and prints whether there is a subset

in A that sums to N or not. Following is a sample code for that.

while(true){

cout << “Enter N: “;

cin >> N;

cout << is_subset_sum(A, N, s) << endl;

Sample input:

5

2 4 5 6 8

Enter N: 15

Enter N: 0

Enter N: 3

Sample output:

15 is a subset sum of the given array

0 is a subset sum of the given array

3 is not a subset sum of the given array

Answer 1

#include <iostream> 
#include<string>


using namespace std;


bool is_subset_sum(int* set, int N, int sum)
{
	bool subset[N+1][sum+1];
	//If sum is 0, then answer is true
	for(int i=0;i<=N;i++)
	{
		subset[i][0]=true;
	}
	// If sum is not 0 and set is empty, then answer is false
	for (int i = 1; i <= sum; i++)
        subset[0][i] = false;
        
    for (int i = 1; i <= N; i++)
	 {
        for (int j = 1; j <= sum; j++)
		{
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j]||subset[i - 1][j - set[i - 1]];
        }
    }
    
	return subset[N][sum];
}


int main()
{
	int arrSz;
	cout<<"Please, enter a number of elements in array: ";
	cin>>arrSz;
	int* arr=new int[arrSz];
	cout<<"Enter elements: ";
	for (int i = 0; i < arrSz; i++)
    {
      cin>>arr[i];
	}
	int summ;
	while(true)
	{
		cout<<"\nEnter summ (0 - exit prigram): ";
		cin>>summ;
		if(summ==0)break;
		if(is_subset_sum(arr,arrSz,summ))
			cout<<summ<<" is a subset summ of the giving array";
		else
			cout<<summ<<" is not a subset summ of the giving array";
	}
}