counting subsets of S so that sum(S_n) = N

Hello,

for all of you following google's group algorithm geeks - yes, this
one has been taken from there :) I've asked the question there without
getting any answer, so I was wondering, If I can get some hints/help
via usenet :-) I've been struggling with this problem for quite a bit
now :


Given the set of integers S = {e_1,e_2 , ... e_n } find (count) all
subsets S_n (please note! this is not a real set in this case, as it
may contain repeated elements!) of S so, that sum(S_n) = N, for a
given integer N.

I've created a lame recursive solution :

=================================================
ways(N, S_n) :
if N == 0
if sort(S_n) not in OC # We consider solutions as {1,3}, {3,1}
only once.
append sorted(S_n) into OC
return 1
else
return 0
ret = 0
for e in S
if N - e < 0
break
append e into S_n
ret += ways(N-e, S_n)
return ret
=================================================

and tested the code in python :
=================================================
2 S = [1,6,4,3,5]
3 oc = []
4 def ways(m,l) :
5 if m == 0 :
6 l.sort()
7 if l not in oc :
8 oc.append(l)
9 return 1
10 else :
11 return 0
12 ret = 0
13 for c in S :
14 if m - c < 0 :
15 break
16 l = [c] + l
17 x = ways(m - c, l)
18 ret += x
19 return ret
20
21 print ways(10,[])
=================================================

The code works fine for small values of N , but crunches all day and
night if supplied with bigger values. I don't see any major way to
optimize this code (except for memonisation, which would be quite
ugly...) so I'm wondering if anyone knows any better approach/
optimisation to handle this problem...

Thanks!

.