Sum of Subset using DP

The “Sum of Subset” problem is a classic example of a combinatorial problem that can be solved using recursion. The objective is to determine whether a subset of the given set of numbers can be found that sums up to a specific target value. This problem is significant in computer science, particularly in the fields of algorithms and complexity theory, can be efficiently solved using Dynamic Programming (DP). Dynamic Programming is particularly useful for this problem as it helps to avoid redundant calculations seen in the pure recursive approach by storing the results of subproblems.

Dynamic Programming Approach:

• We create a 2D array dp where each element dp[i][j] represents whether there exists a subset of the first i numbers in the set S that sums up to j.
• The dimensions of this array are (n+1) x (sum+1), where n is the number of elements in the set and sum is the target sum we’re trying to achieve.
• The value of dp[i][j] is true if a subset exists with sum j using the first i items, otherwise false.

Initialization:

• The first column of dp, which represents the target sum 0, is initialized to true because the empty subset always sums to 0.
• The first row, except for dp[0][0], is initialized to false because we cannot achieve a positive sum with zero elements.

Filling the DP Table:

• For each element set[i-1], we determine whether to include it in the subset or not based on the values already computed and stored in the table.

fun isSubsetSum(set: IntArray, n: Int, sum: Int): Boolean {
    // dp[i][j] will be true if there is a subset of set[0..i-1] with sum j
    val dp = Array(n + 1) { BooleanArray(sum + 1) }

    // Initialize top row as true, as 0 sum is possible with all elements.
    for (i in 0..n) {
        dp[i][0] = true
    }

    // Fill the subset table in a bottom-up manner
    for (i in 1..n) {
        for (j in 1..sum) {
            // If the current element is more than the sum, we copy the value from the above row
            if (set[i - 1] > j) dp[i][j] = dp[i - 1][j]
            else {
                // Include the element or exclude it
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - set[i - 1]]
            }
        }
    }

    return dp[n][sum]
}

// Example usage
fun main() {
    val set = intArrayOf(3, 34, 4, 12, 5, 2)
    val sum = 9
    val n = set.size

    if (isSubsetSum(set, n, sum))
        println("Found a subset with given sum")
    else
        println("No subset with given sum")
}

Explanation:

• The function isSubsetSum initializes a 2D Boolean array dp where dp[i][j] represents the existence of a subset with sum j using the first i items of the set.
• It first initializes all positions of dp[i][0] to true because a sum of 0 can always be achieved with an empty subset.
• The main nested loops fill the DP table. For each item set[i-1] and each target sum j, it checks if the current item is greater than j. If it is, it copies the value from the previous row (excluding the current item). Otherwise, it checks if any of the two conditions (including or excluding the current item) can achieve the target sum.
• The final answer to the problem is found at dp[n][sum], which indicates whether a subset with the target sum exists within the entire set.