ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน
ปรับปัญหาการแบ่งพาร์ทิชันให้อยู่ในรูปกระเป๋าเป้ 0/1 ที่มีเป้าหมายเป็นผลรวมทั้งหมด/2 และตรวจสอบความเป็นไปได้ด้วยอาร์เรย์ DP แบบบูลีน
ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
โจทย์ปัญหา
กำหนดอาร์เรย์จำนวนเต็มบวกที่ไม่ว่างเปล่า nums ให้ตรวจสอบว่าสามารถแบ่งอาร์เรย์ออกเป็น เซตย่อยสองชุดที่มีผลรวมเท่ากัน ได้หรือไม่ ตัวอย่างเช่น [1, 5, 11, 5] สามารถแบ่งเป็น [1, 5, 5] และ [11] ซึ่งต่างมีผลรวมเท่ากับ 11 หากผลรวมทั้งหมดเป็นเลขคี่ คำตอบจะเป็น False ทันที มิฉะนั้น เราต้องหาเซตย่อยที่มีผลรวมเท่ากับ total_sum // 2 ซึ่งเป็นปัญหาผลรวมเซตย่อยแบบคลาสสิก
การลดรูปเป็นปัญหาผลรวมของเซตย่อย
การลดรูปที่สำคัญคือ หากผลรวมทั้งหมด S เป็นจำนวนคู่ และมีเซตย่อยที่มีผลรวมเป็น S//2 สมาชิกที่เหลือจะมีผลรวมเป็น S//2 โดยอัตโนมัติ ดังนั้น ปัญหาการแบ่งอาร์เรย์เป็นเซตย่อยที่มีผลรวมเท่ากันจึงลดรูปเป็นคำถามว่า มีเซตย่อยใดของอาร์เรย์ตัวเลขที่มีผลรวมเป็น S//2 หรือไม่ นี่คือปัญหา ผลรวมของเซตย่อย แบบ NP สมบูรณ์สุดคลาสสิก ซึ่งเราแก้ได้ด้วย DP แบบกระเป๋าเป้ 0/1 ในเวลา O(n × S)
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?อาร์เรย์ DP แบบบูลีน
กำหนดอาร์เรย์บูลีน dp[c] โดย dp[c] = True หมายความว่ามีเซตย่อยที่มีผลรวมเท่ากับ c พอดี เริ่มต้นด้วย dp[0] = True (เซตย่อยว่างมีผลรวมเป็น 0) และกำหนดค่าอื่นทั้งหมดเป็น False สำหรับตัวเลขแต่ละตัว num ให้วนความจุจาก target ลงมาถึง num (การวนซ้ำย้อนกลับของกระเป๋าเป้ 0/1) แล้วกำหนดค่า dp[c] = dp[c] or dp[c - num]
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # Falseไล่ตามตัวอย่าง
สำหรับ [1, 5, 11, 5] ผลรวมทั้งหมดเป็น 22 และเป้าหมายเป็น 11 เริ่มต้นด้วย dp[0]=True หลังประมวลผลเลข 1: dp[1]=True หลังประมวลผลเลข 5: dp[5]=True, dp[6]=True หลังประมวลผลเลข 11: dp[11]=True (ใช้เลข 11 เพียงตัวเดียว) เราพบค่าที่ดัชนี 11 เป็นจริงแล้ว แต่ยังคงประมวลผลตัวเลขทั้งหมดต่อ คำตอบสุดท้ายคือ dp[11]=True ดังนั้นจึงสามารถแบ่งได้
การปรับปรุงด้วยการยุติก่อนกำหนด
เราสามารถเพิ่มการออกจากการทำงานก่อนกำหนดได้ดังนี้ หาก dp[target] กลายเป็น True ณ จุดใดก็ตาม ให้คืนค่า True ทันที วิธีนี้อาจช่วยเร่งกรณีที่ดีที่สุดได้อย่างมาก นอกจากนี้ หากสมาชิกใดมีค่าเท่ากับ target เราก็คืนค่า True ได้ทันที หากสมาชิกใดมีค่ามากกว่า target สมาชิกนั้นจะไม่สามารถอยู่ในเซตย่อยใดที่มีผลรวมเป็นเป้าหมายได้ แต่เรายังคงต้องตรวจสอบสมาชิกที่เหลือ
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # Trueการใช้เซตของไพธอนแทนอาร์เรย์ DP
อีกทางเลือกหนึ่งคือเก็บรักษา เซตของผลรวมที่เป็นไปได้ เริ่มต้นด้วย {0} สำหรับตัวเลขแต่ละตัว ให้นำตัวเลขนั้นไปบวกกับผลรวมทุกค่าในเซตปัจจุบัน: reachable = reachable | {s + num for s in reachable} จากนั้นกรองให้เหลือเฉพาะผลรวมที่ไม่เกินเป้าหมาย เมื่อจบการทำงาน ให้ตรวจสอบว่าเป้าหมายอยู่ในเซตหรือไม่ วิธีนี้เข้าใจได้ง่าย แต่ในการใช้งานจริงอาจใช้หน่วยความจำมากกว่าและทำงานช้ากว่า
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # Trueการวิเคราะห์ความซับซ้อน
วิธี DP ทำงานใน เวลา O(n × S) โดยที่ S = sum(nums) และใช้ พื้นที่ O(S) สำหรับอาร์เรย์บูลีน ภายใต้ข้อจำกัดของ LeetCode (n ≤ 200, ผลรวม ≤ 20,000) จะมีการดำเนินการมากที่สุด 4,000,000 ครั้ง ซึ่งถือว่าเร็วมาก วิธีใช้เซตมีความซับซ้อนเชิงเส้นกำกับเหมือนกัน แต่ในการใช้งานจริงอาจช้ากว่าเนื่องจากมีค่าใช้จ่ายในการสร้างเซต
การสรุปทั่วไป: การนับเซตย่อยที่มีผลรวม
ปัญหาที่เกี่ยวข้องคือการนับจำนวนเซตย่อยที่มีผลรวมเป็นเป้าหมาย เปลี่ยน DP จากบูลีนเป็นจำนวนเต็ม: dp[c] = number of ways to reach sum c ใช้การบวกแทน OR: dp[c] += dp[c - num] เริ่มต้นด้วย dp[0] = 1 และใช้การวนซ้ำย้อนกลับเหมือนเดิม การสรุปทั่วไปนี้แสดงให้เห็นว่าแม่แบบกระเป๋าเป้สามารถปรับใช้กับคำถามเกี่ยวกับเซตย่อยที่แตกต่างกันได้อย่างไร
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))คำถามต่อยอดที่พบบ่อยในการสัมภาษณ์
ควรเตรียมตอบคำถามต่อยอดต่อไปนี้: (1) หากต้องคืนค่าการแบ่งจริง จะทำอย่างไร — ต้องใช้ DP 2 มิติเพื่อสร้างคำตอบย้อนกลับ (2) หากสมาชิกอาจเป็นจำนวนลบ จะทำอย่างไร — เลื่อนเป้าหมาย หรือใช้พจนานุกรมแทนอาร์เรย์ (3) ความซับซ้อนด้านเวลาคือเท่าใด — O(n × ผลรวม) (4) หากมีตัวเลขซ้ำกันจำนวนมาก จะปรับปรุงได้หรือไม่ — ได้ โดยใช้การนับความถี่เพื่อลดจำนวนรอบการวนซ้ำภายนอก ควรกล่าวถึงข้อแลกเปลี่ยนเหล่านี้ไว้ล่วงหน้าเสมอ
การเชื่อมโยงกับกระเป๋าเป้ 0/1
ปัญหาการแบ่งอาร์เรย์เป็นเซตย่อยที่มีผลรวมเท่ากันเป็นการประยุกต์ใช้กระเป๋าเป้ 0/1 โดยตรง: สิ่งของคือบรรดาตัวเลข น้ำหนักเท่ากับค่า และความจุของกระเป๋าเป้เท่ากับเป้าหมาย เราถามว่าค่าสูงสุดเท่ากับเป้าหมายหรือไม่ (ความเป็นไปได้) ไม่ได้ถามว่าค่าสูงสุดคือเท่าใด การวนซ้ำย้อนกลับเหมือนเดิม สิ่งที่เปลี่ยนมีเพียงการดำเนินการจาก max เป็นบูลีน or การมองเห็นความเชื่อมโยงนี้ในการสัมภาษณ์แสดงให้เห็นว่าคุณมองหารูปแบบได้ดี
กรณีขอบ
กรณีขอบที่ต้องจัดการ ได้แก่ (1) อาร์เรย์ที่มีความยาว 1 — สมาชิกเพียงตัวเดียวไม่สามารถแบ่งออกเป็นสองส่วนได้ จึงเป็น False เสมอ (2) สมาชิกทุกตัวเหมือนกันและมีจำนวนเป็นคู่ — อาจแบ่งได้หรือไม่ได้ ขึ้นอยู่กับค่าของสมาชิกแต่ละตัว (3) ผลรวมที่มีขนาดใหญ่มาก — ตรวจสอบข้อจำกัดก่อนจัดสรรอาร์เรย์ DP (4) สมาชิกที่มีค่ามากกว่าเป้าหมาย — ข้ามได้ เพราะไม่มีทางเป็นส่วนหนึ่งของเซตย่อยที่มีผลรวมเป็นเป้าหมาย การตรวจสอบสมาชิกที่มีค่าสูงสุดเพื่อยุติการทำงานก่อนกำหนดจะจัดการกรณี (4) ได้อย่างมีประสิทธิภาพ
ตรวจสอบความเข้าใจอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดเรื่องโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า ปัญหาการแบ่งอาร์เรย์เป็นเซตย่อยที่มีผลรวมเท่ากันลดรูปเป็นปัญหาผลรวมของเซตย่อย โดยมีเป้าหมาย = ผลรวมทั้งหมด//2 DP 1 มิติแบบบูลีน dp[c] ใช้การวนซ้ำย้อนกลับเช่นเดียวกับกระเป๋าเป้ 0/1 และ วิธีนี้สรุปทั่วไปไปสู่การนับเซตย่อยได้โดยแทนที่บูลีน OR ด้วยการบวกจำนวนเต็ม ต่อไปเราจะศึกษาเรื่องเส้นทางสั้นที่สุดด้วยอัลกอริทึม Dijkstra และคิวลำดับความสำคัญ
คำถามที่พบบ่อย
บทเรียน “ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน”
ปรับปัญหาการแบ่งพาร์ทิชันให้อยู่ในรูปกระเป๋าเป้ 0/1 ที่มีเป้าหมายเป็นผลรวมทั้งหมด/2 และตรวจสอบความเป็นไปได้ด้วยอาร์เรย์ DP แบบบูลีน คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ
- กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II
- ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน
- ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ