Sum of Subset using Recursion

by

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, as it is closely related to the NP-complete problems, making it a valuable case study for understanding recursive algorithms and their applications.

Given:

  • A set (or array) of integers, S.
  • A target sum value, target.

The task is to find:

  • Whether there exists a subset of S whose sum is equal to target.

Characteristics:

  • The elements in the subset must be distinct and taken from the set S.
  • The subset can be of any size, ranging from 0 to the size of S.
  • The same number from the set S cannot be used more than once in the subset.

This problem is inherently recursive, as each element in the set has two choices: either to be included in the subset or to be excluded. This creates a binary decision tree, which can be explored using recursion.

Recursive Approach

  1. Base Cases:
    • If the target sum becomes 0, it means we have found a subset whose sum matches the target. Return true.
    • If the set is empty or if we have considered all elements and the target sum is not 0, return false.
  2. Recursive Step:
    • For each element in the set, we have two choices: include it in the current subset or exclude it.
    • To explore both choices, we make two recursive calls: a. Including the current element and reducing the target sum by the value of the current element. b. Excluding the current element and not altering the target sum.
  3. Combining Results:
    • If either recursive call returns true, we can conclude that a subset summing up to the target exists.
Kotlin
fun isSubsetSum(set: IntArray, n: Int, sum: Int): Boolean {
    // Base Cases
    if (sum == 0) return true
    if (n == 0) return false

    // If the last element is greater than sum, then ignore it
    if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum)

    /* Now, we have two cases:
    1. Include the last element, reduce sum by the value of 'set[n-1]' and decrease the count of elements
    2. Exclude the last element, do not change the sum and decrease the count of elements
    */
    return isSubsetSum(set, n - 1, sum - set[n - 1]) || isSubsetSum(set, n - 1, 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 takes three parameters: the set set, the number of elements in the set n, and the target sum sum.
  • It first checks the base cases: if sum is 0, it returns true; if n is 0, it returns false.
  • If the current element is greater than the sum, it is ignored by recursively calling the function without including the current element.
  • The recursive step involves two calls: one including the current element (and thus reducing the sum by its value) and the other excluding it. The function returns true if either of the recursive calls returns true.
  • The main function demonstrates an example usage of the isSubsetSum function, printing whether a subset with the given sum exists or not.

Leave a Comment