SumToTarget.swift

//
// Description: Finds the sum of all elements that add up to the target value using dynamic programming.
// Note: input array must be non negative and constrained to a reasonable ranage because it uses target+1 memory 
//
// Language: Swift
//
// Author: Paul Ossenbruggen
// Date: Nov 10, 2015
//

import Foundation



func countSubElementsThatAddUpToTargetDP(target : Int, array : [Int]) -> Int {
    var numWaysToSumToN = [Int](count: target + 1, repeatedValue: 0)
    numWaysToSumToN[0] = 1
    for val in array {
        let prevTarget = target - val
        if prevTarget < 0 {
            continue
        }
        for num in (0...prevTarget).reverse() {
            numWaysToSumToN[num + val] += numWaysToSumToN[num]
        }
    }
    print(numWaysToSumToN)
    return numWaysToSumToN[target]
}
countSubElementsThatAddUpToTargetDP(9, array: [1, 2, 3, 4, 5, 6, 7, 8, 9])
countSubElementsThatAddUpToTargetDP(9, array: [9, 5, 2, 4, 3, 9, 2])
countSubElementsThatAddUpToTargetDP(9, array: [1, 3, 2, 5, 4, 9])
countSubElementsThatAddUpToTargetDP(9, array: [1, 3, 2, 5, 4, 6])
countSubElementsThatAddUpToTargetDP(9, array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])