I have good experience solving such stuff with a branch and bound algorithm combined with clever normalization (i.e. grouping similar cases) and caching in a hash (no need to descend a sub-tree which has already been investigated before).

In this case the normalization would be the sum of the partial solution, which would also be the key in the cache-hash.

for instance: 2+3 = 5 so once you can cache all further path for 5 without needing to branch.

2+3   +95 => $cache{5} = [ [95] ]

5     +95 => seen!

HTH! :)

PS: I wrote many posts about branch-and-bound here try searching the archives if interested.