Thinking on conventional lines, [I would not go with the generation of all subsets since we could potentially gather some info from subsets already generated until a point], my search would be tree based - each node representing one of the intial N numbers we are given. Each node would have an attribute called "sum" attached to it.
The "sum" attribute at a particular node is calculated as follows - it is the sum of the numbers in the nodes from the root to that node (hence can be calculated incrementally). The search would prune based on whether the "sum" atttribute goes > "s" (refer to sudhakar-aluri's post above) This algo would turn out to be a nice recursive one with o(n) space since at any point of time it will maintain only one path from root to a leaf. Infact, I guess it incorporates of bit of dp as well since "sum" attributes are reused in the traversals in subtrees ;)
