Find a subset of the given array with a given sum

Given an input array and a sum value as inputs and the algorithm needs to find whether there exists a subset of the input array which sums up to a given sum. Let’s try to understand the problem with some example input values.

Experiment 1:
Input: {10, 4, 19, 8, 2, 12, 5}, sum = 7
Output: Subset Exists with Sum 7: TRUE

Explanation: As per the input array there exists an input array {2, 5} which sums up to 7 which is equal to the given sum.
Input array with highlighted values sum as 7.

The should be a recursive solution to this problem. Let’s write a math function to get a better understanding of the solution.

f(i, l, s) = f(i,l-1,s) // if element in l-1 is > sum
(or)
f(i, l, s) = f(i,l-1,s) || f(i,l-1,s-i[l-1]) // for all other cases.

Enough MATH, lets try to solve this problem with some code

#include <iostream>

using namespace std;

// Recursive approve to find subset.
bool subSetExists(int inp[], int len, int sum)
{
	if(sum == 0) return true;
	if(len == 0 && sum != 0)	return false;

	if(inp[len-1] > sum) 
		return subSetExists(inp, len-1, sum);

	return subSetExists(inp, len-1, sum) ||
		 subSetExists(inp, len-1, sum - inp[len-1]);
}

// Driver program
int main(int argc, char* argv[])
{
	int inp[] = {10, 4, 19, 8, 2, 12, 5};
	int len = sizeof(inp) / sizeof(inp[0]);
	bool hasSubset = subSetExists(inp, len, 7);
	cout<<"Subset Exists with Sum 7: "
		<<((hasSubset == true)?"TRUE":"FALSE")<<endl;
	return 0;
}
Output:
Subset Exists with Sum 7: TRUE

Complexity: O(n^2)Space: O(1)

Simple enough…hmm but wait, code seems simple but when considering the complexity this algorithm has a lot of overlaps which causes performance worst. To reduce the overlaps I can only think of dynamic programming solutions.

What we do special in dynamic programming to reduce the overlaps? The answer is very simple, we store the results of each function in an array and reuse them when algorithm needs again. It needs extra space with better performance. Now let us see the code with dynamic programming.

#include <iostream>

using namespace std;

bool subsetArraySum(int inp[], int len, int sum)
{
	bool dp[len][sum+1];
	
	for(int i=0; i<=sum; i++)
	{
		dp[0][i] = (inp[0] == i);
	}
	for(int i=1; i<len; i++)
	{
		for(int j=0; j<=sum; j++)
		{
			dp[i][j] = (inp[i] == j) || dp[i-1][j];
			if(j > inp[i])
				dp[i][j] |= dp[i-1][j-inp[i]];
		}
	}
	return dp[len-1][sum];
}

int main(int argc, char* argv[])
{
	int inp[] = {5, 2, 10, 12, 9, 21};
	int len = sizeof(inp) / sizeof(inp[0]);
	int sum = 15;
	
	int result = subsetArraySum(inp, len, sum);
	cout<<"Subarray with sum 15 found: "
		<<((result == true)?"TRUE":"FALSE")<<endl;
	return 0;
}
Output:
Subarray with sum 15 found: TRUE

Complexity: O(n),
Space: O(1)

These are the two different solutions I can think of now. Please try to understand the problem and solve it with recursion first then jump to dynamic programming. If you have any better approach to solve this problem please let readers know by commenting on here. Cheers!.

Advertisements