# My Weblog

## Project Euler 103

Project Euler Problem 103 . I started solving this problem assuming that given algorithm will not produce correct result for n= 7. I took the search space [20..50] and generated all the combination of 7. For each combination , i generated all the subsets and checked for the property
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

S(B) S(C); that is, sums of subsets cannot be equal.
If B contains more elements than C then S(B) S(C).

According to my complexity analysis , the complexity of brute force algorithm is O ( (50-20+1) Choose 7 * ( n + n^2 ) ) where n = 2^7 which is O( 31 Choose 7 * n^2 ) = 43 082 956 800. I wrote a Haskell solution and after running it 2 hours on my five years old PC , it did not produce any result .Searching on net , a blog suggested that given algorithm on Euler will work for n = 7 and it will produce optimal solution and to my complete surprise it worked. In the forum no one brute forced it in Haskell so i am not sure if its possible to solve this problem in Haskell. Brute force algorithm did not produce the result on my PC but may be on faster PC it can produce result . subset and combination codes are borrowed from David Tran’s blog.
Edit : Improved brute force using sorting the subsets based on their sum. Now answer is withing couple of minutes. Complexity O( 25 Choose 7 * n log n) where n = 2^7. Go Haskell go 🙂

```import Data.List

subset::[a] ->[[a]]
subset [] = [[]]
subset (x:xs) = subset xs ++ map (x:)  (subset xs)

combination :: [a] -> Int -> [[a]]
combination _   0    = [[]]
combination []  _    = []
combination (x:xs) n = ( map (x:)  (combination xs (n-1)) ) ++ combination xs n

fun ::(Num a, Ord a ) => [a] -> [a] -> Bool
fun y x =
case intersect y x == []  of
True ->   if ( if l_a > l_b then s_a > s_b else if l_a < l_b then  s_a < s_b else s_a /= s_b )  then True else False where
s_a = sum y
s_b = sum x
l_a = length y
l_b = length x
_    -> True

checkOptimum ::(Num a , Ord a ) => [a] -> Bool
checkOptimum xs = optimumHelper  (sortBy (\a b -> compare ( sum a ) ( sum b) ) . tail.subset \$ xs )   where
optimumHelper [x,y] = if fun x y then True else False
optimumHelper  (x:y:ys)  = if fun x y  then optimumHelper  (y:ys) else False

main = do
let lst_1 = filter checkOptimum \$ combination [20..45] 7
ans = foldl' (\(acc , list )  x -> if  sum x  < acc then ( sum x  , x )  else ( acc , list) ) ( 1000 , [] ) lst_1
print ans
```

Haskell code which produced result .

```import Data.List

m :: [Integer]
m = [0,11, 18, 19, 20, 22, 25]

solve = concatMap show . map (+20) \$ m
```