สร้างเซตย่อยทั้งหมด

โจทย์การแข่งขันจำนวนมากขอให้ลองเซตย่อยทุกเซตของเซตขนาดเล็ก การเรียกซ้ำช่วยให้แสดงรายการทั้งหมดได้อย่างเป็นระเบียบและเชื่อถือได้ 🧩

แนวคิดหลักคือ สำหรับสมาชิกแต่ละตัว ให้สร้างทางเลือกแบบไบนารีหนึ่งครั้งว่าจะรวมสมาชิกนั้นไว้หรือไม่นำมารวม ทางเลือกครบทุกชุดจะให้เซตย่อยหนึ่งเซต

เซตที่มีสมาชิก n ตัวจะมี2 ยกกำลัง n เซตย่อยพอดี เพราะสมาชิกแต่ละตัวทำให้จำนวนเพิ่มเป็นสองเท่า ดังนั้นควรรักษา n ให้เล็ก ประมาณ 20 หรือน้อยกว่า

เลื่อนดัชนีไปตามอาร์เรย์ ที่แต่ละดัชนีให้แตกกิ่งสองทาง ได้แก่ เลือกสมาชิกหนึ่งทาง และข้ามสมาชิกอีกทาง

เมื่อดัชนีเลยสมาชิกตัวสุดท้าย เส้นทางปัจจุบันคือเซตย่อยที่สมบูรณ์หนึ่งเซต ช่วงเวลานั้นคือกรณีฐานสำหรับบันทึกเซตย่อย

การไล่สำรวจแบบเรียกซ้ำนี้บันทึกเซตย่อยที่จุดสิ้นสุด แล้วสำรวจทางเลือกข้ามและเลือกจากแต่ละดัชนี

เมื่อใช้ append เพื่อเพิ่มสมาชิก ให้ลบสมาชิกนั้นออกหลังการเรียกซ้ำ เพื่อให้กิ่งถัดไปเริ่มต้นอย่างสะอาด ขั้นตอนการยกเลิกนี้คือหัวใจของการย้อนกลับ

นอกจากนี้ยังสามารถจับคู่จำนวนเต็มแต่ละจำนวนตั้งแต่ 0 ถึง 2 ยกกำลัง n ลบ 1 กับเซตย่อยหนึ่งเซต โดยให้แต่ละบิตระบุว่าสมาชิกตัวใดถูกรวมไว้

จัดเก็บสำเนาของรายการปัจจุบันเสมอ ไม่ใช่ตัวรายการเอง มิฉะนั้นการเปลี่ยนแปลงภายหลังจะเขียนทับเซตย่อยทุกเซตที่บันทึกไว้ ⚠️

หากต้องการเซตย่อยที่มีขนาดคงที่ k ให้หยุดกิ่งเมื่อจำนวนสมาชิกที่เลือกถึง k วิธีนี้จะเปลี่ยนการสร้างเซตย่อยให้เป็นการสร้าง combinations

การแจกแจงเซตย่อยใช้แก้ปัญหากระเป๋าเป้ขนาดเล็ก การเลือกทีม และการตรวจสอบความเป็นไปได้ที่ต้องทดสอบตัวเลือกทุกแบบ

เซตที่มีสมาชิก n ตัวจะมีเซตย่อยกี่เซต

ได้เรียนรู้การแสดงรายการเซตย่อยทั้งหมดด้วยการเลือกหรือข้ามสมาชิกแต่ละตัว และยกเลิกการเลือกหลังแต่ละกิ่ง ควรรักษา n ให้เล็ก เพราะจำนวนเซตคือ 2 ยกกำลัง n 🎯