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(n

^{2})

**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(2

^{n})

## No comments:

## Post a Comment