Rash thoughts about .NET, C#, F# and Dynamics NAV.

The “Subset Sum”-problem is given as the following:

SUBSET SUM
Input: Numbers a₁, a₂, . . . , a_n, S ∈ N.
Question: Is there a subset I ⊆ {1,…,n} with ∑ a_i = S?

Finding a solution for this decision problem is a very easy task in F#.

let hasSubsetSum_Naive (numbers: int list) S =
  let rec hasSubsetSum (a: int list) lastSum =
    match a with 
      | [] -> false
      | x::rest -> 
        if lastSum + x = S then
          true
        elif lastSum + x > S then
          false
        else
          hasSubsetSum rest lastSum || hasSubsetSum rest (lastSum+x)
  
  hasSubsetSum numbers 0

let numbers = [ 5;4;3;6;7;12 ]
let searchedSum = 33  
hasSubsetSum_Naive numbers searchedSum

Of course this small program can be easily adjusted to give the subset I back. Unfortunately this naïve approach leads to a running time of O(2^n).

But if S is small we can build a dynamic program and decide the problem in O(n*S) time.

This can be easily transformed into F# code.

let hasSubsetSum (numbers: int array) S =
   if numbers |> Array.exists (fun x -> x = S) then
     true
   else
     let a = numbers |> Array.filter (fun x -> x < S)      
     let n = a.Length
     if n = 0 then
       false
     else
       let v = Array2.create n (S+1) 0
       let u = Array2.create n (S+1) false
       let t = Array2.create n (S+1) 0
       
       for j in [1..S] do
         for i in [0..n-1] do                           
           if j - a.[i] >= 0 && not u.[i,j - a.[i]] then
             v.[i,j] <- t.[i,j - a.[i]] + a.[i]
           if ((i = 0) || (i > 0 && t.[i-1,j] <> j)) && v.[i,j] = j then
             u.[i,j] <- true
           if v.[i,j] = j then
             t.[i,j] <- j
           else
             if i > 0 then
               t.[i,j] <- max t.[i-1,j] t.[i,j-1]
             else
               t.[i,j] <- t.[0,j-1]
               
       t.[n-1,S] = S