Kiểm tra mảng có thể chia thành hai mảng con với hiệu tuyệt đối bằng K trong Python

Cho mảng input_list và số n. Kiểm tra xem có thể cắt mảng thành hai phần liên tiếp sao cho hiệu tuyệt đối của tổng hai phần bằng n hay không.

Ví dụ: input_list = [9,2,5,6], n=0 → cắt sau phần tử 2: tổng trái=11, tổng phải=11 → hiệu 0 → "Possible".

Giải thuật

• Tính tổng toàn mảng list_total.
• Nếu (list_total - n) % 2 == 1 → "Not Possible".
• Giá trị mục tiêu cho nửa đầu: val = (list_total - n) / 2.
• Duyệt tích lũy tổng, nếu bằng val → "Possible".

Mã ví dụ

def solve(input_list, n):
    list_total = sum(input_list)
    if (list_total - n) % 2 == 1:
        return "Not Possible"
    val = (list_total - n) / 2
    temp_sum = 0
    for i in range(len(input_list)):
        temp_sum += input_list[i]
        if temp_sum == val:
            return "Possible"
    return "Not Possible"

input_list = [9,2,5,6]
n = 0
print(solve(input_list, n))

Đầu vào

[9,2,5,6], 0

Đầu ra

Possible