अस्वीकरण: नीचे वर्णित विधि सार्वभौमिक नहीं है, लेकिन यह अक्सर समस्या का समाधान कर सकती है या आपको सही समाधान तक पहुंचने में मदद कर सकती है।
यदि आपको किसी समस्या में क्रमचय के अस्तित्व की जांच करने की आवश्यकता है, या मेल खाने वाले क्रमपरिवर्तन की संख्या, या कुछ समान खोजने की आवश्यकता है, तो आपको गतिशील सबसेट प्रोग्रामिंग का उपयोग करने पर विचार करना चाहिए।
मुख्य पैरामीटर एक बिटमास्क होगा, जो दिखाएगा कि कौन से तत्व पहले से क्रमचय में शामिल किए गए हैं और कौन से नहीं हैं। इसके अलावा अक्सर एक दूसरे पैरामीटर की आवश्यकता होती है जो इंगित करता है कि कौन सा तत्व सबसे अंत में शामिल किया गया था।
ग्राफ़ में पथ के संदर्भ में अक्सर क्रमपरिवर्तन देखे जा सकते हैं। तदनुसार, आइए एक उत्कृष्ट उदाहरण पर विचार करें - हैमिल्टनियन पथ समस्या।
एक हैमिल्टनियन पथ एक सरल पथ है जो ग्राफ के प्रत्येक शीर्ष से ठीक एक बार गुजरता है। इसे केवल लंबाई n के क्रमचय के रूप में दर्शाया जा सकता है, जहाँ n शीर्षों की संख्या है। इस क्रमचय के भीतर का क्रम उस क्रम को इंगित करेगा जिसमें इस पथ में शीर्षों को पार किया जाता है।
ग्राफ़ में हैमिल्टनियन पथ की उपस्थिति की जाँच करने के लिए, आइए डायनामिक्स dp[mask][last] शुरू करें - क्या कोई सरल पथ है जो मास्क बिटमास्क में चिन्हित शीर्षों को बायपास करता है और अंतिम शीर्ष पर समाप्त होता है।
प्रारंभिक मान होंगे dp[2i][i] = सत्य, बाकी असत्य, जिसका अर्थ है कि किसी भी कोने से शुरू होने वाला हमेशा एक खाली रास्ता होता है।
डीपी [मुखौटा] [अंतिम] में मूल्य सही होने से हम "पथ का विस्तार" के अर्थ में बदलाव को आगे बढ़ाएंगे। यही है, हम उन शीर्षों की संख्या की तलाश करेंगे जो मुखौटा में शून्य के साथ चिह्नित हैं (हमने अभी तक उन्हें रास्ते में नहीं देखा है) और एक ही समय में ऐसा है कि अंतिम से इस शीर्ष तक एक किनारा है (पथ होना चाहिए) मौजूदा किनारे से बढ़ाया जा सकता है)। यानी हम dp[mask | 2k][k] = true अगर dp[mask][last] = true AND mask & 2k = 0 (शीर्ष k अभी तक नहीं देखा गया है) और अंत में एक किनारा है -> क.
अंततः, एक हैमिल्टनियन पथ मौजूद है यदि dp में सभी बिटमास्क और किसी भी अंतिम शीर्ष के मापदंडों के लिए एक सही मान है।