This post has already been read 5691 times!

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.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True //There is a subset (4, 5) with sum 9.

Let **isSubSetSum(int set[], int n, int sum)** be the **function **to find whether there is a **subset of set[]** with sum equal to **sum**.

**n **is the number of elements in set[].

The **isSubsetSum problem** can be divided into **two subproblems** :

Include the last element, recur forn = n-1, sum = sum – set[n-1]Exclude the last element, recur forn = n-1

If any of the above the above subproblems return true, then return true.

# Recursive formula for **isSubsetSum()** problem

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || isSubsetSum(arr, n-1, sum-set[n-1]) Base Cases 1. isSubsetSum(set, n, sum) = false, ifsum > 0 and n == 02. isSubsetSum(set, n, sum) = true, ifsum == 0

# Naive recursive implementation that simply follows the recursive structure mentioned above

// Returns true if there is a subset of set[] with sun equal to given sum function isSubsetSum($set, $n, $sum) { // Base Cases if ($sum == 0) return true; if ($n == 0 && $sum != 0) return false; // If last element is greater than sum, then ignore it if ($set[$n-1] > $sum) return isSubsetSum($set, $n-1, $sum); /* else, check if sum can be obtained by any of the following (a) including the last element (b) excluding the last element */ return isSubsetSum($set, $n-1, $sum) || isSubsetSum($set, $n-1, $sum-$set[$n-1]); }

Found a subset with given sum

The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).