सबसेट सम समस्या कंप्यूटर विज्ञान और गतिशील प्रोग्रामिंग में एक क्लासिक समस्या है। सकारात्मक पूर्णांकों के एक सेट और एक लक्ष्य योग को देखते हुए, कार्य यह निर्धारित करना है कि क्या दिए गए सेट का एक उपसमूह मौजूद है जिसके तत्व लक्ष्य योग में जुड़ते हैं।

सबसेट सम समस्या के लिए PHP प्रोग्राम

पुनरावर्ती समाधान का उपयोग करना

उदाहरण

 $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.";
?>

आउटपुट

Found a subset with the given sum.
No subset with the given sum.

प्रदान किए गए उदाहरण में, सेट [1, 7, 4, 9, 2] है, और लक्ष्य योग 16 और 25 हैं। 25 के लक्ष्य योग के साथ दूसरा कॉल गलत रिटर्न देता है, जो दर्शाता है कि कोई उपसमुच्चय नहीं है यह 25 तक जुड़ जाता है। इसलिए आउटपुट पहली कॉल में दिए गए योग के साथ एक सबसेट मिला। दूसरी कॉल में दिए गए योग के साथ कोई उपसमुच्चय नहीं।

डायनेमिक प्रोग्रामिंग का उपयोग करते हुए छद्म-बहुपद समय

उदाहरण

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

आउटपुट

Found a subset with given sum.

प्रदान किए गए उदाहरण में, सेट [8, 15, 26, 35, 42, 59] है, और लक्ष्य योग 50 है। फ़ंक्शन कॉल isSubsetSum($set, $ n, $sum) सत्य लौटाता है, यह दर्शाता है कि सेट में एक उपसमुच्चय [8, 42] मौजूद है जो 50 के लक्ष्य योग तक जुड़ जाता है। इसलिए, कोड का आउटपुट होगा दिए गए योग के साथ एक उपसमुच्चय मिला।

निष्कर्ष

निष्कर्षतः, उपसमुच्चय योग समस्या को हल करने के लिए दो अलग-अलग दृष्टिकोण हैं। पहला समाधान एक पुनरावर्ती दृष्टिकोण है जो जांच करता है कि लक्ष्य योग के बराबर योग के साथ दिए गए सेट का कोई उपसमूह है या नहीं। यह सभी संभावित संयोजनों का पता लगाने के लिए बैकट्रैकिंग का उपयोग करता है। हालाँकि, इस समाधान में सबसे खराब स्थिति में घातीय समय जटिलता हो सकती है।

दूसरा समाधान गतिशील प्रोग्रामिंग का उपयोग करता है और सबसेट योग समस्या को नीचे से ऊपर तरीके से हल करता है। यह मध्यवर्ती परिणामों को संग्रहीत करने के लिए एक तालिका बनाता है और कुशलतापूर्वक निर्धारित करता है कि दिए गए योग के साथ कोई उपसमूह मौजूद है या नहीं। इस दृष्टिकोण में O(n*sum) की समय जटिलता है, जो इसे पुनरावर्ती समाधान की तुलना में अधिक कुशल बनाती है। दोनों दृष्टिकोणों का उपयोग सबसेट योग समस्या को हल करने के लिए किया जा सकता है, जिसमें गतिशील प्रोग्रामिंग समाधान बड़े इनपुट के लिए अधिक कुशल है।