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. ?> |
Output:
Found a subset with given sum
Please refer complete article on Subset Sum Problem | DP-25 for more details!
<!–
–>
Php Program for Minimum product subset of an array
Php Program For Chocolate Distribution Problem
PHP Program for Largest Sum Contiguous Subarray
Php Program to Find maximum value of Sum( i*arr[i]) with only rotations on given array allowed
Php Program for Maximum sum of i*arr[i] among all rotations of a given array
Php Program for Maximum circular subarray sum
Php Program for Size of The Subarray With Maximum Sum
Php Program for Maximum equilibrium sum in an array
Php Program to Find a triplet such that sum of two equals to third element
Php Program for Count pairs with given sum
Article Contributed By :
neveropen
Vote for difficulty
Improved By :
Article Tags :
Report Issue
<!–
Please write us at contribute@geeksforgeeks.org to report any issue with the above content
–>
Please Login to comment…