import Data.List

main :: IO ()
main =
  mapM_ (print . find4A)
        [
          "1 5 3 6 : 10"
        , "1 5 3 6 7 : 10"
        , "1 2 3 4 5 : 10"
        , "1 2 3 4 5 6 7 8 : 10"
        ]

find4A :: String -> [String]
find4A s = filter ((== y) . eval4A) exprs
  where
    exprs     = combo $ [x1] : map addOperators xs
    x1:xs     = words xs0
    y         = read $ tail y0
    (xs0, y0) = break (==':') s
    addOperators :: String -> [String]
    addOperators x = map (++ x) [" + ", " - ", " * ", " / "]

combo :: [[[a]]] -> [[a]]
combo (x:xs) = combo' x xs
  where
    combo' ys []    = ys
    combo' ys (h:t) = combo' [y ++ z | y <- ys, z <- h] t
combo _      = []

eval4A :: String -> Double
eval4A s = go (map read xxs) yys
  where
    (xxs, yys) = partition (`notElem` ["+", "-", "*", "/"]) $ words s
    go [x1]       _        = x1
    go (x1:x2:xs) ("*":ys) = go ((x1 * x2) : xs) ys
    go (x1:x2:xs) ("/":ys) = go ((x1 / x2) : xs) ys
    go (x1:xs)    ("+":ys) = x1 + go xs ys
    go (x1:x2:xs) ("-":ys) = x1 + go ((-x2) : xs) ys
    go _          _        = -1