Java Programming – Subset Sum Problem

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
…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.

[ad type=”banner”]

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || 
                           isSubsetSum(set, n-1, sum-set[n-1])
Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0 

Following is naive recursive implementation that simply follows the recursive structure mentioned above.

[pastacode lang=”java” manual=”%2F%2F%20A%20recursive%20solution%20for%20subset%20sum%20problem%0Aclass%20subset_sum%0A%7B%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20there%20is%20a%20subset%20of%20set%5B%5D%20with%20sum%0A%20%20%20%20%20%20%20%20%2F%2F%20equal%20to%20given%20sum%0A%20%20%20%20static%20boolean%20isSubsetSum(int%20set%5B%5D%2C%20int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20%20%20%20%20if%20(sum%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20if%20(n%20%3D%3D%200%20%26%26%20sum%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%2F%2F%20If%20last%20element%20is%20greater%20than%20sum%2C%20then%20ignore%20it%0A%20%20%20%20%20%20%20if%20(set%5Bn-1%5D%20%3E%20sum)%0A%20%20%20%20%20%20%20%20%20return%20isSubsetSum(set%2C%20n-1%2C%20sum)%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%2F*%20else%2C%20check%20if%20sum%20can%20be%20obtained%20by%20any%20of%20the%20following%0A%20%20%20%20%20%20%20%20%20%20(a)%20including%20the%20last%20element%0A%20%20%20%20%20%20%20%20%20%20(b)%20excluding%20the%20last%20element%20%20%20*%2F%0A%20%20%20%20%20%20%20return%20isSubsetSum(set%2C%20n-1%2C%20sum)%20%7C%7C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20isSubsetSum(set%2C%20n-1%2C%20sum-set%5Bn-1%5D)%3B%0A%20%20%20%20%7D%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20set%5B%5D%20%3D%20%7B3%2C%2034%2C%204%2C%2012%2C%205%2C%202%7D%3B%0A%20%20%20%20%20%20%20%20%20%20int%20sum%20%3D%209%3B%0A%20%20%20%20%20%20%20%20%20%20int%20n%20%3D%20set.length%3B%0A%20%20%20%20%20%20%20%20%20%20if%20(isSubsetSum(set%2C%20n%2C%20sum)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Found%20a%20subset%20with%20given%20sum%22)%3B%0A%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%20subset%20with%20given%20sum%22)%3B%0A%20%20%20%20%7D%0A%7D” message=”Java” highlight=”” provider=”manual”/]

Output :

 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).

[ad type=”banner”]

We can solve the problem in Pseudo-polynomial time using Dynamic programming. 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] [pastacode lang=”java” manual=”%2F%2F%20A%20Dynamic%20Programming%20solution%20for%20subset%20sum%20problem%0Aclass%20subset_sum%0A%7B%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20there%20is%20a%20subset%20of%20set%5B%5D%20with%20sun%20equal%20to%20given%20sum%0A%20%20%20%20static%20boolean%20isSubsetSum(int%20set%5B%5D%2C%20int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20value%20of%20subset%5Bi%5D%5Bj%5D%20will%20be%20true%20if%20there%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20is%20a%20subset%20of%20set%5B0..j-1%5D%20with%20sum%20equal%20to%20i%0A%20%20%20%20%20%20%20%20boolean%20subset%5B%5D%5B%5D%20%3D%20new%20boolean%5Bsum%2B1%5D%5Bn%2B1%5D%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20sum%20is%200%2C%20then%20answer%20is%20true%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20subset%5B0%5D%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20sum%20is%20not%200%20and%20set%20is%20empty%2C%20then%20answer%20is%20false%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20subset%5Bi%5D%5B0%5D%20%3D%20false%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Fill%20the%20subset%20table%20in%20botton%20up%20manner%0A%20%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20subset%5Bi%5D%5Bj%5D%20%3D%20subset%5Bi%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(i%20%3E%3D%20set%5Bj-1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20subset%5Bi%5D%5Bj%5D%20%3D%20subset%5Bi%5D%5Bj%5D%20%7C%7C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20subset%5Bi%20-%20set%5Bj-1%5D%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F*%20%2F%2F%20uncomment%20this%20code%20to%20print%20table%0A%20%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20printf%20(%22%254d%22%2C%20subset%5Bi%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20%20%7D%20*%2F%0A%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20return%20subset%5Bsum%5D%5Bn%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20int%20set%5B%5D%20%3D%20%7B3%2C%2034%2C%204%2C%2012%2C%205%2C%202%7D%3B%0A%20%20%20%20%20%20%20%20%20%20int%20sum%20%3D%209%3B%0A%20%20%20%20%20%20%20%20%20%20int%20n%20%3D%20set.length%3B%0A%20%20%20%20%20%20%20%20%20%20if%20(isSubsetSum(set%2C%20n%2C%20sum)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Found%20a%20subset%20with%20given%20sum%22)%3B%0A%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22No%20subset%20with%20given%20sum%22)%3B%0A%20%20%20%20%7D%0A%7D” message=”Java” highlight=”” provider=”manual”/]

Output:

Found a subset with given sum

Time complexity of the above solution is O(sum*n).

[ad type=”banner”]