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

 $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
";
else
   echo "No subset with the given sum
";
$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

= $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 

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.