Thursday, April 16, 2015

Subset Sum

Given an array of non-negative integers and a value determine if there is a subset of the given array with sum equal to given value.

Dynamic Programming Solution:

Maintain a Boolean 2D matrix say table[][] where the value of table[i][j] will be true if there is a subset of array[0..j-1] with sum equal to i, otherwise false. Obviously table[sum][n] will be our answer.

Implementation:

bool isSubsetSum(int *arr, int len, int sum)
{
if(sum == 0)
return true;
if(arr == NULL || len == 0)
return false;

bool **table = new bool *[sum + 1];
for(int i = 0; i <= sum; ++i)
{
table[i] = new bool[len+1];
}

for(int i = 0; i <= len; ++i)
table[0][i] = true;
for(int i = 1; i <= sum; ++i)
table[i][0] = false;

for(int i = 1; i <= sum; ++i)
{
for(int j = 1; j <= len; ++j)
{
table[i][j] = table[i][j-1];
if(i >= arr[j-1])
{
table[i][j] = table[i][j] || table[i - arr[j-1]][j-1];
}
}
}
return table[sum][len];
}

Complexity: O(n2)

Limitation: You can see that this solution is not feasible if the sum is too big (Too much memory consumption).


Another approach:

Try all the subsets of the given array and check whether sum of the elements in the subset is equal to given sum or not.

Implementation:

bool isSubsetSum(int *arr, int len, int sum)
{
if(sum == 0)
return true;
if(arr == NULL || len == 0)
return false;
if(arr[len-1] > sum)
return isSubsetSum(arr, len - 1, sum);

return isSubsetSum(arr, len - 1, sum) || isSubsetSum(arr, len - 1, sum - arr[len -1]);
}

Complexity: O(2n)

No comments:

Post a Comment