One of my colleagues at Jayway launched a functional puzzle and solicited responses via Github gists. The challenge was as follows:

- Write a function that, given a sequence of either positive or negative integers, returns true if
*any*subset of the list sums up to zero. Eg:

find-solutions ([-7 4 3 8 -5]) => true

find-solutions ([-6 2 3]) => false - Make it work with any number, not just zero. Eg:

find-solutions (0, [-7 4 3 8 -5]) => true

find-solutions (13, [-7 4 3 8 -5]) => false - Make it return all matching sequences, instead of a boolean. Eg:

find-solutions (0, [-7 4 3 8 -5]) => [ [-7 4 3] [-7 4 8 -5] ]

find-solutions (13, [-7 4 3 8 -5]) => [] - Make it take any predicate for the sum, not just equal to a number. Eg:

find-solutions (isZero, [-7 4 3 8 -5]) => [ [-7 4 3] [-7 4 8 -5] ]

find-solutions (isOdd, [-7 4 3]) => [ [-7] [3] [-7 4] [4 3] ]

Of course, me being an F# n00b I ended up at StackOverflow within hours of trying my hand at this, and I also asked among code monkeys on Facebook, so I will not submit an answer is it wouldn’t be my own. My colleagues went ahead and figured out solutions on their own rather than use Google engineering like I did.

Anyway, as you can imagine, the first bit is the hard one. With higher order functions, delegating the actual filtering is done easily thereafter by supplying the comparer function as a parameter.

So what do you do? I looked at many solutions, but couldn’t manage to use the comme il faut solution with a permutation tree, but went with a list of permutations instead which I then could trivially recurse through to see if I ever find a match.

If you are using Google engineering to solve F# problems, be aware that the old function Seq.map_concat has been renamed Seq.collect, which is a clear improvement.

In my case I found my permutation function on StackOverflow, provided by the excellent Tomáš Petříček, see blogroll, and just added my c0dez to find matches. This is from a console app, so hence the EntryPoint business.

let rec permutations list taken = seq { if Set.count taken = List.length list then yield [] else for l in list do if not (Set.contains l taken) then for perm in permutations list (Set.add l taken) do yield l::perm } let rec isMakingZero acc lst = match lst with | [] -> false | a :: tail -> (acc + a = 0) || isMakingZero (acc + a) tail let rec testpaths pathlist = if Seq.length pathlist = 0 then false else isMakingZero 0 (Seq.head pathlist) || testpaths (Seq.skip 1 pathlist) [<EntryPoint>] let main argv = printfn "First %A" (testpaths (permutations [1; -2; 3; -5] Set.empty)) printfn "Second %A" (testpaths (permutations [1; -3; 2; -5] Set.empty)) 0 // return an integer exit code

As you can imagine, you just supply a function to testpaths that then gets passed down to isMakingZero, which should be renamed, in order to solve the remaining tasks.