प्रत्येक संभावित सबसेट

Question

पिछली बार मुझे दिलचस्प समस्या मिली, और मैं उस पर फंस गया।

एन संख्याओं को एक [1], ..., एक [एन] आरोही क्रम में और संख्या के (1 < = एन, के < = 10^5) दिया गया।

मान लें कि हम योग द्वारा दिए गए अनुक्रम के प्रत्येक संभावित सबसेट को सॉर्ट कर रहे हैं।
हमें इस तरह के सबसेट के के-वें मिलना होगा।

उदाहरण के लिए:
एन = 4 k = 8
एक = {2, 7, 8, 15}

1: {2}, योग = 2
2: { 7}, योग = 7
3: {8}, योग = 8
4: {2, 7}, योग = 9
5: {2, 8}, योग = 10
6: {7, 8}, योग = 15
7: {15}, योग = 15
8: {2, 15}, योग = 17
...
के = 8, तो उत्तर = 17 (सबसेट {2,15})।

बेशक हम ओ (2^एन * एन) में हर संभावित सबसेट और पूरे समाधान चला सकते हैं, लेकिन मैं कुछ और अधिक स्मार्ट-रैखिक, या कम से कम ओ (एनके) खोज रहा हूं।

Answer 1

(खाली सबसेट हैंडलिंग सादगी के लिए अरिक्त सबसेट ग्रहण करने के लिए जा रहे हैं। एक या दो लाइन है।)

सूचकांक S एक गैर खाली उपसम्मुच्य को देखते हुए, बच्चों S की परिभाषित S \ {max(S)} U {max(S) + 1} और S U {max(S) + 1} किया जाना है। {1} से शुरू होने से, बाल संबंध एक पेड़ बनाता है जिसमें सकारात्मक पूर्णांक के प्रत्येक nonempty सबसेट शामिल है।

{1} 
| \ 
{2} {1,2}______ 
| \  \  \ 
{3} {2,3} {1,3} {1,2,3} 

संबंधित सरणी तत्वों के योग द्वारा कुंजी, यह पेड़ एक न्यूनतम ढेर है। यदि आप सावधानी से चाबियाँ (स्क्रैच से संक्षेप में जोड़ने और घटाने के द्वारा) की गणना करते हैं और मिनी-ढेर हटाने को आलसी रूप से कार्यान्वित करते हैं, तो आपको ओ (के लॉग लॉग) -टाइम एल्गोरिदम मिलता है।