It can be reduced to subset sum problem. So I cannot see O(n) being possible here. Even the dynamic programming approach(provided there are some more constraints for this problem) is O(n*m) where m is related to the range of values of sum.
On Aug 7, 2:10 pm, swetha rahul <[email protected]> wrote: > Given an array find all the set which form the given sum in O(n) > > i/p: a[]={1,2,3,5,7,6,8,10} > sum=9 > > o/p should be {1,3,5} {2,7} {3,6},{1,8} -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
