In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: Given a set of non-negative integers and an integer s, does any non-empty subset sum to s? Subset sum can also be thought of as a special case of the knapsack problem. One interesting special case of subset sum is the partition problem, in which s is half of the sum of all elements in the set.
Let isSubsetSum(int set[], int n, int s) be the function to find whether there is a subset of set[] with sum equal to s, where n is the number of elements in set[].
The isSubsetSum problem can be divided into two subproblems
(a) Include the last element, recur for n = n-1, sum = sum – set[n-1] (b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.
We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i, otherwise false. Finally, we return subset[sum][n].
For example, for n = 4 set = {3,2,7,1} and s = 6
The answer is true.