Chương trình chia tập hợp thành hai tập con có tổng bằng nhau và mọi phần tử tập đầu nhỏ hơn tập sau bằng Python

Giả sử chúng ta có một danh sách số gọi là nums, chúng ta cần kiểm tra xem có thể chia danh sách thành hai nhóm A và B sao cho: Tổng của A và tổng của B bằng nhau. Mọi số trong A đều nhỏ hơn chặt chẽ mọi số trong B.

Ví dụ, nếu đầu vào là nums = [3, 4, 5, 12], thì đầu ra sẽ là True, vì ta có thể có A = [3,4,5] và B = [12] và cả hai đều có tổng là 12.

Quy trình giải quyết

1. Sắp xếp danh sách nums.
2. Tính total = tổng tất cả các phần tử trong nums.
3. Khởi tạo s = 0, i = 0.
4. Trong khi i < len(nums):
   • n = nums[i].
   • Trong khi i < len(nums) và nums[i] == n:
     • s += nums[i].
     • i += 1.
   • Nếu s == total - s, trả về True.
5. Trả về False.

Ví dụ mã nguồn

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

Đầu vào

[3, 4, 5, 12]

Đầu ra

True