### 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