find total subset sums to s
given an array of elements (all elements are unique ) , given a sum s find all the subsets having sum s. for ex array
{5,9,1,3,4,2,6,7,11,10} sum is 10 possible subsets are {10}, {6,4}, {7,3}, {5,3,2}, {6,3,1} etc. there can be many more. also find the total number of these subsets.
//arr[0],arr[1]....arr[n-1] are array elements and given sum is s.
ReplyDeletesubset(arr,n,s)=subset(arr,n-1,s) U subset(arr,n-1,s-arr[n-1])
count(arr,n,sum)=count(arr,n-1,sum)+count(arr,n-1,sum-arr[n-1])
Boundary conditions:
count(arr,1,sum)=1, if sum=arr[0]
=0, otherwise
subset(arr,1,sum)={sum}, if sum=arr[0]
=NULL, otherwise