Greplin Challenge #3 Set Sums

import Data.Array.ST; import Control.Monad.ST; import Data.Array
import Control.Monad
import Data.List

numbers = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

sources = reverse $ init numbers

{- Dynamic programming: build a table for

   14 15 16 ... 99    (because 3, 4, 9 cannot be a sum)
3
4
9
..
97
(because 99 cannot participate in a sum)

For each entry, we fill in the combinations that can sum to the target.
Start from the last row, we have:
f(i, j) = if i>=j, []
          else if i = j, [i]
          else, f(next_i, j) || f(next_i, j-i)

Notice that we only reference the row right below us, so we could use a 1-D array instead of a 2-D table.
Build the table bottom up, right to left.

-}

buildTable :: Array Int [[Int]]
buildTable = runSTArray $ do
  targets <- newArray (14,99) []
  let f i = mapM_ g $ reverse [14 .. 99]
        where g j = when (i <= j) $ do
                if (i == j) then writeArray targets j [[i]]
                 else unless (j-i < 14) $ do
                      not_take_i <- readArray targets j
                      take_i <- readArray targets (j-i)
                      case take_i of
                           [] -> return ()
                           _ -> writeArray targets j $ union not_take_i $ map (i:) take_i
  mapM_ f sources
  return targets

filterTable = zip numbers $ map f numbers
  where f x = if x <= 14 then []
              else let sets = buildTable!x in
                   filter g sets
        g xs = case xs of
                       [_] -> False
                       _ -> True

answer = sum $ map length $ snd $ unzip filterTable

{- A brute force solution isn't that slow either:

main = print $ length . filter (\x -> sum x `elem` a) . filter (\x -> length x > 1) $ subsequences a
  where a = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99]

-}