PHP Program for Subset Sum Problem

The Subset Sum Problem is a classic problem in computer science and dynamic programming. Given a set of positive integers and a target sum, the task is to determine whether there exists a subset of the given set whose elements add up to the target sum.

PHP Program for Subset Sum Problem

Using recursive solution

Example

<?php
// A recursive solution for the subset sum problem
// Returns true if there is a subset of the set
// with a sum equal to the given sum
function isSubsetSum($set, $n, $sum)
{
   // Base Cases
   if ($sum == 0)
      return true;
   if ($n == 0 && $sum != 0)
      return false;
   // If the last element is greater than the sum, then ignore it
   if ($set[$n - 1] > $sum)
      return isSubsetSum($set, $n - 1, $sum);
   // Check if the sum can be obtained by either including or excluding the last element
   return isSubsetSum($set, $n - 1, $sum) ||
      isSubsetSum($set, $n - 1, $sum - $set[$n - 1]);
}
// Driver Code
$set = array(1, 7, 4, 9, 2);
$sum = 16;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum<br>";
else
   echo "No subset with the given sum<br>";
$sum = 25;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum.";
else
   echo "No subset with the given sum.";
?>

Output

Found a subset with the given sum.
No subset with the given sum.

In the provided example, the set is [1, 7, 4, 9, 2], and the target sums are 16 and 25. The second call with a target sum of 25 returns false, indicating that there is no subset that adds up to 25.so the output came as Found a subset with the given sum in first call. No subset with the given sum in second call.

Pseudo-polynomial time using Dynamic programming

Example

<?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(8,15,26,35,42,59);
$sum = 50;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
	echo "Found a subset with given sum.";
else
	echo "No subset with given sum.";
?>

Output

Found a subset with given sum.

In the provided example, the set is [8, 15, 26, 35, 42, 59], and the target sum is 50. The function call isSubsetSum($set, $n, $sum) returns true, indicating that there exists a subset [8, 42] in the set that adds up to the target sum of 50.Therefore, the output of the code would be Found a subset with the given sum.

Conclusion

In conclusion, there are two different approaches to solve the subset sum problem. The first solution is a recursive approach that checks if there is a subset of the given set with a sum equal to the target sum. It utilizes backtracking to explore all possible combinations. However, this solution may have exponential time complexity in the worst case.

The second solution utilizes dynamic programming and solves the subset sum problem in a bottom-up manner. It constructs a table to store intermediate results and efficiently determines if a subset with the given sum exists. This approach has a time complexity of O(n*sum), making it more efficient than the recursive solution. Both approaches can be used to solve the subset sum problem, with the dynamic programming solution being more efficient for larger inputs.

The above is the detailed content of PHP Program for Subset Sum Problem. For more information, please follow other related articles on the PHP Chinese website!