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.


  1. //arr[0],arr[1]....arr[n-1] are array elements and given sum is s.

    subset(arr,n,s)=subset(arr,n-1,s) U subset(arr,n-1,s-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


Post a Comment

Popular posts from this blog