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!
Hot AI Tools
Undress AI Tool
Undress images for free
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1794
16
1740
56
1591
29
1473
72
267
587
How to use PHP to build social sharing functions PHP sharing interface integration practice
Jul 25, 2025 pm 08:51 PM
The core method of building social sharing functions in PHP is to dynamically generate sharing links that meet the requirements of each platform. 1. First get the current page or specified URL and article information; 2. Use urlencode to encode the parameters; 3. Splice and generate sharing links according to the protocols of each platform; 4. Display links on the front end for users to click and share; 5. Dynamically generate OG tags on the page to optimize sharing content display; 6. Be sure to escape user input to prevent XSS attacks. This method does not require complex authentication, has low maintenance costs, and is suitable for most content sharing needs.
PHP integrated AI intelligent picture recognition PHP visual content automatic labeling
Jul 25, 2025 pm 05:42 PM
The core idea of integrating AI visual understanding capabilities into PHP applications is to use the third-party AI visual service API, which is responsible for uploading images, sending requests, receiving and parsing JSON results, and storing tags into the database; 2. Automatic image tagging can significantly improve efficiency, enhance content searchability, optimize management and recommendation, and change visual content from "dead data" to "live data"; 3. Selecting AI services requires comprehensive judgments based on functional matching, accuracy, cost, ease of use, regional delay and data compliance, and it is recommended to start from general services such as Google CloudVision; 4. Common challenges include network timeout, key security, error processing, image format limitation, cost control, asynchronous processing requirements and AI recognition accuracy issues.
PHP creates a blog comment system to monetize PHP comment review and anti-brush strategy
Jul 25, 2025 pm 08:27 PM
1. Maximizing the commercial value of the comment system requires combining native advertising precise delivery, user paid value-added services (such as uploading pictures, top-up comments), influence incentive mechanism based on comment quality, and compliance anonymous data insight monetization; 2. The audit strategy should adopt a combination of pre-audit dynamic keyword filtering and user reporting mechanisms, supplemented by comment quality rating to achieve content hierarchical exposure; 3. Anti-brushing requires the construction of multi-layer defense: reCAPTCHAv3 sensorless verification, Honeypot honeypot field recognition robot, IP and timestamp frequency limit prevents watering, and content pattern recognition marks suspicious comments, and continuously iterate to deal with attacks.
How to use PHP combined with AI to achieve text error correction PHP syntax detection and optimization
Jul 25, 2025 pm 08:57 PM
To realize text error correction and syntax optimization with AI, you need to follow the following steps: 1. Select a suitable AI model or API, such as Baidu, Tencent API or open source NLP library; 2. Call the API through PHP's curl or Guzzle and process the return results; 3. Display error correction information in the application and allow users to choose whether to adopt it; 4. Use php-l and PHP_CodeSniffer for syntax detection and code optimization; 5. Continuously collect feedback and update the model or rules to improve the effect. When choosing AIAPI, focus on evaluating accuracy, response speed, price and support for PHP. Code optimization should follow PSR specifications, use cache reasonably, avoid circular queries, review code regularly, and use X
PHP calls AI intelligent voice assistant PHP voice interaction system construction
Jul 25, 2025 pm 08:45 PM
User voice input is captured and sent to the PHP backend through the MediaRecorder API of the front-end JavaScript; 2. PHP saves the audio as a temporary file and calls STTAPI (such as Google or Baidu voice recognition) to convert it into text; 3. PHP sends the text to an AI service (such as OpenAIGPT) to obtain intelligent reply; 4. PHP then calls TTSAPI (such as Baidu or Google voice synthesis) to convert the reply to a voice file; 5. PHP streams the voice file back to the front-end to play, completing interaction. The entire process is dominated by PHP to ensure seamless connection between all links.
How to use PHP to combine AI to generate image. PHP automatically generates art works
Jul 25, 2025 pm 07:21 PM
PHP does not directly perform AI image processing, but integrates through APIs, because it is good at web development rather than computing-intensive tasks. API integration can achieve professional division of labor, reduce costs, and improve efficiency; 2. Integrating key technologies include using Guzzle or cURL to send HTTP requests, JSON data encoding and decoding, API key security authentication, asynchronous queue processing time-consuming tasks, robust error handling and retry mechanism, image storage and display; 3. Common challenges include API cost out of control, uncontrollable generation results, poor user experience, security risks and difficult data management. The response strategies are setting user quotas and caches, providing propt guidance and multi-picture selection, asynchronous notifications and progress prompts, key environment variable storage and content audit, and cloud storage.
How to use PHP to develop AI-driven advertising delivery PHP advertising performance optimization solution
Jul 25, 2025 pm 06:12 PM
PHP provides an input basis for AI models by collecting user data (such as browsing history, geographical location) and pre-processing; 2. Use curl or gRPC to connect with AI models to obtain click-through rate and conversion rate prediction results; 3. Dynamically adjust advertising display frequency, target population and other strategies based on predictions; 4. Test different advertising variants through A/B and record data, and combine statistical analysis to optimize the effect; 5. Use PHP to monitor traffic sources and user behaviors and integrate with third-party APIs such as GoogleAds to achieve automated delivery and continuous feedback optimization, ultimately improving CTR and CVR and reducing CPC, and fully implementing the closed loop of AI-driven advertising system.
PHP integrated AI speech recognition and translator PHP meeting record automatic generation solution
Jul 25, 2025 pm 07:06 PM
Select the appropriate AI voice recognition service and integrate PHPSDK; 2. Use PHP to call ffmpeg to convert recordings into API-required formats (such as wav); 3. Upload files to cloud storage and call API asynchronous recognition; 4. Analyze JSON results and organize text using NLP technology; 5. Generate Word or Markdown documents to complete the automation of meeting records. The entire process needs to ensure data encryption, access control and compliance to ensure privacy and security.
