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

## Sunday, 7. December 2008

### SubsetSum in O(nS)

Filed under: English posts,F#,Informatik — Steffen Forkmann at 13:17 Uhr

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

SUBSET SUM
Input: Numbers a1, a2, . . . , an, S Ã¢Ë†Ë† N.
Question: Is there a subset I Ã¢Å â€  {1,…,n} with Ã¢Ë†â€˜ ai = 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```
Tags: , , ,