Example: SubSetSum - rFronteddu/general_wiki GitHub Wiki

In the isSubsetSum method, you are trying to determine whether there exists a subset of the given array arr that adds up to the given sum sum.

// V  total ->
//    0 1 2 3 4 5 6 7 8 9 10 11
// 2  T F T F F F F F F F  F  F
// 3  T F T T F T F F F F  F  F
// 7  T F T T F T F T F T  F  F
// 8  T F T T F T F T T T  F  T
// 10 T F T T F T F T T T  F  T

// arr index go from 1 to arr.len
subSetSum(arr, total)
    n = arr.len
    // index go from 0 to n and from 0 to total
    let dp[0..n, 0..total] be a new table
    for i = 0 to n
        dp[i, 0] = T
    for i = 1 to n
        for j = 1 to total
            if j < arr[i]
                dp[i,j] = dp[i-1,j]
            else
                dp[i,j] = dp[i-1,j] || dp[i-1, j-arr[i]]

    // Backtrack to find the elements
    elements = []
    i = n
    j = total
    while i > 0 and j > 0
        if dp[i,j] && !dp[i-1,j]
            elements.push(arr[i])
            j = j - arr[i]
        i = i - 1

    // Print the elements
    print("Subset with sum ", total, "is: ")
    for element in elements
        print(element)


    return dp[n, total]