Kiểm tra phân hoạch mảng thành K mảng con liên tiếp bằng tổng (Python)

Bài toán: Cho mảng nums và K. Kiểm tra có thể chia mảng thành K mảng con liền tiếp (contiguous) có tổng bằng nhau không.

Triển khai Python

def solve(nums, k):
    n = len(nums)
    # Tính prefix sum
    cumul_sum = [0] * n
    cumul_sum[0] = nums[0]
    for i in range(1, n):
        cumul_sum[i] = cumul_sum[i - 1] + nums[i]
    
    total_sum = cumul_sum[n - 1]
    if total_sum % k != 0:
        return False
    
    target = total_sum // k
    count = 0
    pos = -1  # vị trí kết thúc partition trước
    
    for i in range(n):
        prev_sum = 0 if pos == -1 else cumul_sum[pos]
        if cumul_sum[i] - prev_sum == target:
            pos = i
            count += 1
        elif cumul_sum[i] - prev_sum > target:
            break
    
    return count == k

# Test
print(solve([2, 5, 3, 4, 7], 3))  # True: [2,5]=7, [3,4]=7, [7]=7
print(solve([1, 2, 3, 4], 2))     # False: total=10, target=5, [1,2,3]>5

Kết quả

True

Giải thích

• Tổng mỗi partition phải = total_sum / K. Nếu không chia hết → False ngay.
• Duyệt mảng, dùng prefix sum kiểm tra tổng từ pos+1 đến i.
• Khi đạt target, cập nhật pos và tăng count.
• Nếu vượt target → break (vì số dương, thêm nữa chỉ lớn hơn).
• Cuối cùng kiểm tra count == K.
• Độ phức tạp: O(n) time, O(n) space (prefix sum).