ตรวจสอบว่าแอรเรย์ของ 1 และ 2 แบ่งเป็น 2 ส่วนที่มีผลรวมเท่ากันได้หรือไม่ใน Python

ภาพรวม

บทความนี้แก้ปัญหา: กำหนดแอรเรย์ที่มีเฉพาะเลข 1 และ 2 ต้องการทราบว่าแบ่งเป็น 2 ส่วนที่มีผลรวมเท่ากันได้หรือไม่

ข้อสังเกตสำคัญ

• ผลรวมทั้งหมดต้องเป็นเลขคู่ (ถ้าเป็นคี่ แบ่งไม่ได้)
• ครึ่งหนึ่งของผลรวม (target) ต้องสามารถสร้างได้จากการรวม 1 และ 2

อัลกอริทึม

1. คำนวณผลรวมทั้งหมด (total) และนับจำนวน 1 (one_count)
2. ถ้า total เป็นคี่ คืนค่า False
3. ถ้า total//2 เป็นเลขคู่ คืนค่า True (เพราะสร้างได้จาก 2 อย่างเดียว)
4. ถ้า total//2 เป็นเลขคี่ ต้องมี 1 อย่างน้อย 1 ตัว เพื่อปรับความเท่าเทียม

ตัวอย่างโค้ด Python

def solve(nums):
    total = sum(nums)
    one_count = nums.count(1)
    if total % 2:
        return False
    if (total // 2) % 2 == 0:
        return True
    if one_count > 0:
        return True
    return False

nums = [1, 1, 2, 2, 2]
print(solve(nums))  # True ([1,1,2] และ [2,2] ผลรวม 4)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

ตรรกะคือ: ถ้าครึ่งผลรวมเป็นคู่ ใช้แค่ 2 ก็ได้ ถ้าเป็นคี่ ต้องมี 1 อย่างน้อย 1 ตัวเพื่อทำให้เป็นคู่ วิธีนี้รวดเร็ว O(n) ไม่ต้องใช้ Dynamic Programming