Hello!
I'd like to present my solution to the problem introduced in the
topic. First thing first, the detailed definition is in place :
Given the set of integers S = {e_1,e_2 , ... e_n } find (count) all
subsets S_n of S so, that sum(S_n) = N, for a given integer N.
After thinking a bit about the problem, I've came up with this
recursive version :
=================================================
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
=================================================
For all of you having a hard time reading this pseudocode, here it is
the Python version :
=================================================
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(100,[])
=================================================
Now, as far as I've tested the code, it works just fine, except for
performance. Converting the recursion to the iterative equivalent
sounds a bit ugly so I tought about using memonisation, but again, the
solution would be ugly as I'd have to use a set as the memonisation
index. I came to the conclusion, that another (better) algorithm
should exists and I'm asking you guys to give me some hints about some
other aproach, or, modification to the existing algorithm, in order to
increase it's performance.
Thanks!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
