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

1. 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
2. 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
3. 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]) => []
4. 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.