Números como suma de N sumandos

José A. Alonso

15-02-2016

Definir la función

sumas :: Int -> [Int] -> [Int]

tal que (sumas n xs) es la lista de los números que se pueden obtener como suma de n, o menos, elementos de xs. Por ejemplo,

sumas 0 [2,5]              ==  [0]
sumas 1 [2,5]              ==  [0,2,5]
sumas 2 [2,5]              ==  [0,2,4,5,7,10]
sumas 3 [2,5]              ==  [0,2,4,5,6,7,9,10,12,15]
sumas 2 [2,3,5]            ==  [0,2,3,4,5,6,7,8,10]
sumas 3 [2,3,5]            ==  [0,2,3,4,5,6,7,8,9,10,11,12,13,15]
length (sumas 8 [1..200])  ==  1601

Soluciones

import Data.List (nub, sort)

sumas :: Int -> [Int] -> [Int]
sumas 0 _  = [0]
sumas n xs = nub (sort (ys ++ [x+y | x <- xs, y <- ys]))
    where ys = sumas (n-1) xs