部分和問題
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 = []