# Solutions for Problem 105

Using the definition of a special sum set from before (see 103), calculate the sum of the sum of all the special sum sets. I.e. S(X1) + S(X2) + ... + S(Xi), where X1 to Xi are the special sum sets.

Runtime: 1.571 seconds

```import Data.List

sets = [{- data from file -}]

{- Returns all possible subsets of a given set -}
allSubs :: [Integer] -> [ [Integer] ]
allSubs [] = []
allSubs (x:xs) = [ [x] ] ++ (map (\z -> [x] ++ z) asxs) ++ asxs
where
asxs = allSubs xs

{- Returns true if a list of integers is unique -}
unique :: [Integer] -> Bool
unique [] = True
unique (x:xs) = (not (elem x xs)) && (unique xs)

{- Checks the second proposition, see below -}
checkProp2 :: [(Integer,Integer)] -> Bool
checkProp2 [] = True
checkProp2 (x:[]) = True
checkProp2 ((lxa,sxa):(lxb,sxb):xs) | lxa == lxb = checkProp2 ([(lxb,sxb)] ++ xs)
checkProp2 ((lxa,sxa):(lxb,sxb):xs) = lcheck && checkProp2 ([(lxb,sxb)] ++ xs)
where
lcheck = foldl (\init (lx,sx) -> init && (sxa < sx)) (sxa < sxb) xs

{- Returns true if a set (represented as a sorted list of integers) is a
- special sum set! To be true it must hold for two properties where B
- and C are disjoint subsets:
- 1. S(B) =/= S(C)
-    The sums of subsets must not be equal
- 2. If |B| > |C| then S(B) > S(C)
-}
isSSS :: [Integer] -> Bool
isSSS [] = False
isSSS xs = prop1 && prop2
where
subs = allSubs xs
prop1 = unique (map sum subs)
lns = sort (map (\x -> (fromIntegral (length x),sum x)) subs)
prop2 = checkProp2 lns

{- Filter all the sets, then calculate the sum of the map of the sum of the
- (now only special sum) sets. -}
main = print (sum (map sum (filter (\x -> isSSS x) sets)))
```

So all the hard work from 103 paid off here. Not wasted after all.