โปรแกรมแบ่งเซตเป็นสองกลุ่มที่มีผลรวมเท่ากันและค่าในกลุ่มแรกน้อยกว่ากลุ่มที่สองด้วย Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums เราต้องตรวจสอบว่าสามารถแบ่งรายการออกเป็นสองกลุ่ม A และ B ได้หรือไม่ โดยที่:

• ผลรวมของ A และผลรวมของ B เท่ากัน
• ทุกตัวเลขใน A น้อยกว่าทุกตัวเลขใน B อย่างเคร่งครัด

ตัวอย่าง: nums = [3, 4, 5, 12] ผลลัพธ์คือ True เพราะสามารถแบ่งได้เป็น A = [3,4,5] และ B = [12] ทั้งคู่มีผลรวมเท่ากับ 12

ขั้นตอนการแก้ปัญหา

1. เรียงลำดับรายการ nums
2. คำนวณ total = ผลรวมของทุกองค์ประกอบใน nums
3. กำหนด s = 0, i = 0
4. วนลูป while i < len(nums):
   • กำหนด n = nums[i]
   • วนลูป while i < len(nums) และ nums[i] == n:
     • s += nums[i]
     • i += 1
   • ถ้า s == total - s คืนค่า True
5. คืนค่า False

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

class Solution:
    def solve(self, nums):
        nums.sort()
        total = sum(nums)
        s = 0
        i = 0
        while i < len(nums):
            n = nums[i]
            while i < len(nums) and nums[i] == n:
                s += nums[i]
                i += 1
            if s == total - s:
                return True
        return False

ob = Solution()
nums = [3, 4, 5, 12]
print(ob.solve(nums))  # Output: True

อินพุต / เอาต์พุต

Input: [3, 4, 5, 12]

Output: True