Published:
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.
# A recursive solution for subset sum
# problem
# Returns true if there is a subset
# of set[] with sun equal to given sum
def isSubsetSum(set,n, sum) :
# Base Cases
if (sum == 0) :
return True
if (n == 0 and 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) or isSubsetSum(set, n-1, sum-set[n-1])
# Driver program to test above function
set = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(set)
if (isSubsetSum(set, n, sum) == True) :
print("Found a subset with given sum")
else :
print("No subset with given sum")
-----
similar another problem
Given an array, find there are 3 numbers have when we add them the value will equals a specified sum Example: {1,4,6,10,20,21} Sum=32, Result:true (1+10+21) Sum=65, Result:false
'''
solution pending
'''
arr = [1,4,6,10,20,21]
sum = 32
isSumMatching(arr, sum, 0,0,0)
more at https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
added on 11-Feb-2018