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 -~----------~----~----~----~------~----~------~--~---