Tìm các giá trị tổng để chia mảng thành các mảng con có tổng bằng nhau trong Python

Cho mảng số nguyên A, ta cần tìm tất cả các giá trị sum sao cho mảng có thể được chia thành các mảng con liên tiếp mà mỗi mảng con có tổng bằng sum. Nếu không chia được, trả về -1.

Ví dụ, với A = [2, 4, 2, 2, 2, 4, 2, 6], kết quả là [6, 8, 12] vì mảng có thể chia thành các mảng con tổng 6, 8, 12.

Thuật toán giải quyết

• Tính mảng tiền tố table.
• S := table[n-1] (tổng toàn mảng).
• Tạo my_map lưu các giá trị tiền tố.
• Duyệt các ước số của S từ 1 đến sqrt(S):
  • Nếu S % i == 0, kiểm tra part_1 = i và part_2 = S // i.
  • Kiểm tra xem các bội của part_1 và part_2 có đều nằm trong my_map không.
  • Nếu có, thêm vào tập kết quả.
• Trả về tập kết quả hoặc -1.

Ví dụ minh họa

from math import sqrt

def find_sum(a):
    n = len(a)
    table = [0] * n
    table[0] = a[0]
    for i in range(1, n):
        table[i] = a[i] + table[i-1]
    S = table[n-1]
    my_map = {}
    for i in range(n):
        my_map[table[i]] = 1
    answer = set()
    for i in range(1, int(sqrt(S)) + 1):
        if S % i == 0:
            is_present = True
            part_1 = i
            part_2 = S // i
            for j in range(part_1, S + 1, part_1):
                if j not in my_map:
                    is_present = False
                    break
            if is_present and part_1 != S:
                answer.add(part_1)
            is_present = True
            for j in range(S // i, S + 1, S // i):
                if j not in my_map:
                    is_present = False
                    break
            if is_present and part_2 != S:
                answer.add(part_2)
    if len(answer) == 0:
        return -1
    return answer

a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))  # {8, 12, 6}

Đầu vào

[2, 4, 2, 2, 2, 4, 2, 6]

Đầu ra

{8, 12, 6}