PHP Program for Subset Sum Problem | DP-25

0 0 3 minutes read

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Example:

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

Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.

Following is naive recursive implementation that simply follows the recursive structure mentioned above.

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 && $sum != 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  
?> 

Output:

Found a subset with given sum

We can solve the problem in Pseudo-polynomial time using Dynamic programming.

PHP

<?php 
// A Dynamic Programming 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) 
{ 
    // The value of subset[i][j] will 
    // be true if there is a subset of 
    // set[0..j-1] with sum equal to i 
    $subset = array(array()); 
  
    // If sum is 0, then answer is true 
    for ( $i = 0; $i <= $n; $i++) 
        $subset[$i][0] = true; 
  
    // If sum is not 0 and set is empty, 
    // then answer is false 
    for ( $i = 1; $i <= $sum; $i++) 
        $subset[0][$i] = false; 
  
    // Fill the subset table in bottom 
    // up manner 
    for ($i = 1; $i <= $n; $i++) 
    { 
        for ($j = 1; $j <= $sum; $j++) 
        { 
            if($j < $set[$i-1]) 
                $subset[$i][$j] =  
                      $subset[$i-1][$j]; 
            if ($j >= $set[$i-1]) 
                $subset[$i][$j] =  
                       $subset[$i-1][$j] ||  
                       $subset[$i - 1][$j -  
                               $set[$i-1]]; 
        } 
    } 
  
    /* // uncomment this code to print table 
    for (int i = 0; i <= n; i++) 
    { 
    for (int j = 0; j <= sum; j++) 
        printf ("%4d", subset[i][j]); 
    printf("n"); 
    }*/
  
    return $subset[$n][$sum]; 
} 
  
// Driver program to test above function 
$set = array(3, 34, 4, 12, 5, 2); 
$sum = 9; 
$n = count($set); 
  
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. 
?> 