gistfile1.txt

Desired Sum: 1 Possible ? false Subset:List()
Desired Sum: 2 Possible ? true Subset:List(List(2))
Desired Sum: 3 Possible ? true Subset:List(List(2, 3))
Desired Sum: 4 Possible ? false Subset:List()
Desired Sum: 5 Possible ? true Subset:List(List(2, 3, 5), List(2, 5))
Desired Sum: 6 Possible ? false Subset:List()
Desired Sum: 7 Possible ? true Subset:List(List(2, 3, 5, 7), List(2, 5, 7), List(2, 7))
Desired Sum: 8 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 9 Possible ? true Subset:List(List(2, 3, 5, 7, 8), List(2, 5, 7), List(2, 7))
Desired Sum: 10 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 11 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 12 Possible ? true Subset:List(List(2, 3, 5, 7, 8), List(2, 5, 7))
Desired Sum: 13 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 14 Possible ? true Subset:List(List(2, 3, 5, 7, 8), List(2, 5, 7))
Desired Sum: 15 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 16 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 17 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 18 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 19 Possible ? false Subset:List()
Desired Sum: 20 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 21 Possible ? false Subset:List()
Desired Sum: 22 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 23 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Desired Sum: 24 Possible ? false Subset:List()
Desired Sum: 25 Possible ? true Subset:List(List(2, 3, 5, 7, 8))
Sum 2 Array List(2)
Sum 2 Array List(2, 7, 5, 3)
Sum 2 Array List(2, 7, 5)
Sum 2 Array List(2, 7, 5, 3, 8)
Sum 2 Array List(2, 7)
Sum 3 Array List(2, 7, 5, 3)
Sum 3 Array List(2, 7, 5, 3, 8)
Sum 5 Array List(2, 7, 5)
Sum 5 Array List(2, 7, 5, 3)
Sum 5 Array List(2, 7, 5, 3, 8)
Sum 7 Array List(2, 7, 5, 3, 8)
Sum 7 Array List(2, 7, 5)
Sum 7 Array List(2, 7, 5, 3)
Sum 7 Array List(2, 7)
Sum 8 Array List(2, 7, 5, 3, 8)
Sum 8 Array List(2, 7, 5, 3)
Sum 9 Array List(2, 7, 5, 3)
Sum 9 Array List(2, 7)
Sum 9 Array List(2, 7, 5, 3, 8)
Sum 9 Array List(2, 7, 5)
Sum 10 Array List(2, 7, 5, 3)
Sum 10 Array List(2, 7, 5, 3, 8)
Sum 11 Array List(2, 7, 5, 3, 8)
Sum 12 Array List(2, 7, 5, 3, 8)
Sum 12 Array List(2, 7, 5, 3)
Sum 12 Array List(2, 7, 5)
Sum 13 Array List(2, 7, 5, 3, 8)
Sum 14 Array List(2, 7, 5)
Sum 14 Array List(2, 7, 5, 3, 8)
Sum 14 Array List(2, 7, 5, 3)
Sum 15 Array List(2, 7, 5, 3)
Sum 15 Array List(2, 7, 5, 3, 8)
Sum 16 Array List(2, 7, 5, 3, 8)
Sum 17 Array List(2, 7, 5, 3, 8)
Sum 17 Array List(2, 7, 5, 3)
Sum 18 Array List(2, 7, 5, 3, 8)
Sum 20 Array List(2, 7, 5, 3, 8)
Sum 22 Array List(2, 7, 5, 3, 8)
Sum 23 Array List(2, 7, 5, 3, 8)
Sum 25 Array List(2, 7, 5, 3, 8)

subsetsum.scala

    // some code to test the two subset sum routines given below
    val list = List(2,7,5,3,8)
    (1 to 25).foreach { sum =>
        val res = IsSubsetSum(list, sum, 0.01)
        println("Desired Sum: " + sum + " Possible ? " + res._1 + " Subset:" + res._2)
    }

    subsetSum(list)
    .filter{ x=> x._2 }
    .keys
    .toList
    .sortBy{ x=> x._2 }
    .foreach{x => println("Sum " + x._2 + " Array " + list.slice(0,x._1+1))}

    /*
    Dynamic Programming Algo for subset Sum ( Ref: Cormen Leiserson)
    Suppose the sequence is x(0), ..., x(N-1)
    and we wish to determine if there is a nonempty subset which sums to zero. 
    Let Q(i, s) = true IFF "there is a nonempty subset of x0, ..., xi which sums to s".
    Let A be the sum of the negative values and B the sum of the positive values. 
    Clearly, Q(i, s) = false, if s < A or s > B. 
    For A ≤ s ≤ B, set Q(1, s) := (x1 == s)
    Then, for i = 2, …, N, set
    Q(i, s) := Q(i − 1, s) or (xi == s) or Q(i − 1, s − xi),  for A ≤ s ≤ B.
    */
    def subsetSum(x:List[Int]) = {
        val N = x.size
        val A = 0
        val B = x.sum
        var Q:Map[(Int, Int), Boolean] = Map()
        (A to B).foreach { s=>
            val key = (0,s)
            val value = (x(0) == s)
            Q = Q ++ Map(key -> value)
        }
        (1 until N).map { i=>
            (A to B).foreach { s=>
                val key = (i,s)
                val key1 = (i-1, s)
                val key2 = (i-1, s - x(i))
                val value = Q.getOrElse(key1, false) || Q.getOrElse(key2,false) || (x(i) == s)
                Q = Q ++ Map(key -> value)
            }
        }
        Q
    }

    /*
      Approx subset sum algo. Ref: 
     if S contains a number between (1 − c)s and s, output yes, otherwise no
     Also return all distinct subsets of x whose sum can generate a number between (1 − c)s and s
    */
     def IsSubsetSum(x:List[Int], s:Double, c:Double):(Boolean, List[List[Int]]) = {
        var S = List(0)
        var ans:List[List[Int]] = List()
        val N = x.size
        (0 until N).foreach { i=>
            val xi = x(i)
            val T = S.map{ y => xi + y }
            val U = {T ++ S}.sorted
            var y = U(0)
            S = List(y)
            U.foreach{ z => 
                if ((y + c*s/N < z) && (z <= s)) {
                    y = z
                    S = S ++ List(z)
                }
            }
            if (S.filter { k => k >= (1-c)*s && k <= s }.size > 0) {
                ans = S.intersect(x)::ans
            }
        }
        (ans.size > 0, ans.distinct)
     }