import Control.Monad

search :: Int -> [Int] -> [[Int]]
search 0 [] = [[]]
search _ [] = []
search target (sz:szs)
    | target < 0  = []
    | target == 0 = [[]]
    | target < sz = search target szs
    | otherwise   = map (sz:) (search (target-sz) szs) ++ search target szs

day17 :: IO ()
day17 = do
    input <- liftM (map read . lines) $ readFile "day17.txt"
    let fullsearch = search 150 input
        minlength  = minimum $ map length fullsearch
        minposs    = filter (\x -> length x == minlength) fullsearch
    print $ length minposs  -- part 1: do fullsearch instead of minposs

main = day17