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 sum of elements equals the target sum.

PHP program for subsets and questions

Use 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 example provided, 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 sums to 25. So the output is Found a subset with the given sum in first call. There is no subset of the given sum in the second call.

Pseudopolynomial 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 example provided, 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 is a subset [8, 42] in the set, which adds up Equal to the target sum of 50. So the code will find the subset with the given sum.

in conclusion

In summary, there are two different ways to solve the subset sum problem. The first solution is a recursive approach that checks if there is a subset of the given set whose sum is equal to the target sum. It uses 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 the intermediate results and effectively determines whether there is a subset with a given sum. This approach has a time complexity of O(n*sum) and is more efficient than the recursive solution. Both methods 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!