部分和問題

30分プログラム、その72。部分和問題。

ある個数の整数の集合Nが存在したとする。

その集合の中から適当な数の整数を選択したとき、 その和が別にあたえられるnになるものが存在するか答えよ。

*Main> part [1,2,3] 3
[[1,2],[2,1],[3]]
*Main> partSum [1,2,2,4] 5
[[1,2,2],[1,2,2],[1,4],[2,1,2],[2,2,1],[2,1,2],[2,2,1],[4,1]]

動いていはいるんだけど、重複があるのが嫌な感じ。

import Data.List
import Control.Monad.List
partSum :: (Num a,Ord a)=> [a]->a->[[a]]
partSum xs sum 
    | sum > 0  = do x <- xs
                    if x == sum 
                     then return [x]
                     else map (x:) (partSum (delete x xs) (sum-x))
    | otherwise = []