418531 ภาคต้น 2552/โจทย์ปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก

ข้อ 1

กำหนดเซตของจำนวนเต็ม $A=\{a_{1},a_{2},\ldots ,a_{n}\}\,$ ที่มีจำนวนสมาชิกเท่ากับ $n\,$ ตัว และกำหนดจำนวนเต็ม $S\,$ มาให้ เราต้องการตรวจสอบว่ามีซับเซต $B\,$ บางซับเซตของ $A\,$ ที่ผลบวกของสมาชิกของมันเท่ากับ $S\,$ หรือไม่

จงออกแบบอัลกอริทึมเพื่อแก้ปัญหาข้างต้น อัลกอริทึมของคุณควรใช้เวลาทำงานไม่เกิน $O(n2^{n})\,$