PHP Program for Subset Sum Problem | DP-25

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.

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 // 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 ?> 

Found a subset with given sum

Time Complexity: O(2ⁿ)
Auxiliary space: O(n)

PHP Program for Subset Sum Problem using Memoization:

As seen in the previous recursion method, each state of the solution can be uniquely identified using two variables – the index and the remaining sum. So create a 2D array to store the value of each state to avoid recalculation of the same state.

Below is the implementation of the above approach:

<?php // Check if possible subset with // given sum is possible or not function subsetSum($a, $n, $sum) { // Storing the value -1 to the matrix $tab = array(); for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $sum; $j++) { $tab[$i][$j] = -1; } } // If the sum is zero, it means // we got our expected sum if ($sum == 0) return 1; if ($n <= 0) return 0; // If the value is not -1, it means it // already called the function // with the same value. // It will save us from repetition. if ($tab[$n - 1][$sum] != -1) return $tab[$n - 1][$sum]; // If the value of a[n-1] is // greater than the sum. // We call for the next value. if ($a[$n - 1] > $sum) return $tab[$n - 1][$sum] = subsetSum($a, $n - 1, $sum); else { // Here we do two calls because we // don't know which value fulfills our criteria. // That's why we're doing two calls. if (subsetSum($a, $n - 1, $sum) != 0 || subsetSum($a, $n - 1, $sum - $a[$n - 1]) != 0) { return $tab[$n - 1][$sum] = 1; } else return $tab[$n - 1][$sum] = 0; } } $n = 5; $a = array(1, 5, 3, 7, 4); $sum = 12; if (subsetSum($a, $n, $sum) != 0) { echo "YES\n"; } else { echo "NO\n"; } ?> 

YES 

Time Complexity: O(sum*n)
Auxiliary space: O(n)

PHP Program for Subset Sum Problem using Dynamic Programming:

We can solve the problem in Pseudo-polynomial time we can use the Dynamic programming approach.

So we will create a 2D array of size (n + 1) * (sum + 1) of type boolean. The state dp[i][j] will be true if there exists a subset of elements from set[0 . . . i] with sum value = ‘j’.

The dynamic programming relation is as follows:

if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]

Below is the implementation of the above approach:

<?php // A Dynamic Programming solution for // subset sum problem // Returns true if there is a subset of // set[] with sum 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]]; } } return $subset[$n][$sum]; } // Driver code $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. ?> 

Found a subset with given sum

Time Complexity: O(sum * n), where n is the size of the array.
Auxiliary Space: O(sum*n), as the size of the 2-D array is sum*n.

PHP Program for Subset Sum Problem using Dynamic Programming with space optimization to linear:

In previous approach of dynamic programming we have derive the relation between states as given below:
if (A[i-1] > j)
dp[i][j] = dp[i-1][j]
else
dp[i][j] = dp[i-1][j] OR dp[i-1][j-set[i-1]]
If we observe that for calculating current dp[i][j] state we only need previous row dp[i-1][j] or dp[i-1][j-set[i-1]].
There is no need to store all the previous states just one previous state is used to compute result.

Step-by-step approach:

• Define two arrays prev and curr of size Sum+1 to store the just previous row result and current row result respectively.
• Once curr array is calculated then curr becomes our prev for the next row.
• When all rows are processed the answer is stored in prev array.

Below is the implementation of the above approach:

<?php function isSubsetSum($set, $n, $sum) { $prev = array_fill(0, $sum + 1, false); for ($i = 0; $i <= $n; $i++) $prev[0] = true; for ($i = 1; $i <= $sum; $i++) $prev[$i] = false; $curr = array_fill(0, $sum + 1, false); for ($i = 1; $i <= $n; $i++) { for ($j = 1; $j <= $sum; $j++) { if ($j < $set[$i - 1]) $curr[$j] = $prev[$j]; if ($j >= $set[$i - 1]) $curr[$j] = $prev[$j] || $prev[$j - $set[$i - 1]]; } $prev = $curr; } return $prev[$sum]; } $set = array(3, 34, 4, 12, 5, 2); $sum = 9; $n = count($set); if (isSubsetSum($set, $n, $sum)) { echo "Found a subset with given sum"; } else { echo "No subset with given sum"; } ?> 

Found a subset with given sum

Time Complexity: O(sum * n), where n is the size of the array.
Auxiliary Space: O(sum), as the size of the 1-D array is sum+1.

Please refer complete article on Subset Sum Problem | DP-25 for more details!