21 May
2007
21 May
'07
7:30 p.m.
Hello, is there an efficient algorithm that takes two positive numbers n and m and that computes all lists l of numbers 0<x<=n such that sum l = m? For instance alg 5 1 = [[1]] alg 5 2 = [[1,1],[2]] alg 5 3 = [[1,1,1],[1,2],[2,1],[3]] ... I know that filter (\l->sum l == m) (powerSet [1..n]) would do the job, however I am looking for a more efficient approach. Help is greatly appreciated, even a google search term would be fine :-) I really hope for a polynomial algorithm although I am not very optimistic about this. Ciao, Steffen