# Euler Solution 103

Jump to: navigation, search

# Solutions for Problem 103

Let A represent a set of size n. With S(X) being the sum of the elements of the set X, and |X| being the number of elements of the set X. Define the string of a set to be the ordered elements of the set described as a non-differentiated string of digits, i.e. {1,3,11} = "1311".

A set is aspecial sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

1. S(B) ≠ S(C)
2. If |B| > |C| then S(B) > S(C)

If S(A) is minimised for a given n, we shall call it an optimum special sum set. Find the string of the optimum special sum set for n = 7.

## Haskell by SanguineV

Runtime: 7.17 ms

```import Data.List

{- 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

{- So I wrote all the code above to check that something is a special sum set.
- Then I used their algorithm to generate a starting position for doing
- manipulations: -}

startset = [20] ++ (map (\x -> x + 20) [11, 18, 19, 20, 22, 25])

{- I checked this and it is indeed a special sum set, put it in to the site
- just in case... and it is the answer. So no examples of how I was
- thinking of reducing or increasing the elements.
-
- ...
-
- Oh well, a stupidly simple way to generate the solution, but at least
- you can check it is optimal, even if not necessarily the smallest one.
-
- So the final total solution code (without all the above) is: -}

main = print (concat (map (\x -> show (x + 20)) [0, 11, 18, 19, 20, 22, 25]))
```

Maybe it will be useful for problems 105 and 106, apparently they are related.