[Haskell-cafe] List algorithm

[Steffen Mazanek]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070521/2dec99dd/attachment.htm