PHP Program for Subset Sum Problem using Recursion

For the recursive approach, there will be two cases.

• Consider the ‘last’ element to be a part of the subset. Now the new required sum = required sum – value of ‘last’ element.
• Don’t include the ‘last’ element in the subset. Then the new required sum = old required sum.

In both cases, the number of available elements decreases by 1.

Step-by-step approach:

• Build a recursive function and pass the index to be considered (here gradually moving from the last end) and the remaining sum amount.
• For each index check the base cases and utilize the above recursive call.
• If the answer is true for any recursion call, then there exists such a subset. Otherwise, no such subset exists.

Below is the implementation of the above approach.

PHP

<?php
// A recursive solution for subset sum problem

// Returns true if there is a subset of set
// with sun equal to given sum
function isSubsetSum($set, $n, $sum)
{
    // Base Cases
    if ($sum == 0)
        return true;
    if ($n == 0)
        return false;
    
    // If last element is greater
    // than sum, then ignore it
    if ($set[$n - 1] > $sum)
        return isSubsetSum($set, $n - 1, $sum);
    
    // Else, check if sum can be 
    // obtained by any of the following
    // (a) including the last element
    // (b) excluding the last element
    return isSubsetSum($set, $n - 1, $sum) || 
        isSubsetSum($set, $n - 1, 
                    $sum - $set[$n - 1]);
}

// Driver Code
$set = array(3, 34, 4, 12, 5, 2);
$sum = 9;
$n = 6;

if (isSubsetSum($set, $n, $sum) == true)
    echo"Found a subset with given sum";
else
    echo "No subset with given sum";
    
// This code is contributed by Anuj_67 
?>

Write a PHP program for a given set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.

Examples:

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
Explanation: There is no subset that adds up to 30.