Kiểm tra tổng mảng có thể bằng K sau ba phép toán trong Python

Cho mảng nums và số K. Mỗi phần tử có thể thực hiện đúng một trong ba phép toán: đổi dấu âm, cộng chỉ số (bắt đầu từ 1), trừ chỉ số. Kiểm tra xem có thể biến đổi mảng sao cho tổng bằng K hay không.

Ví dụ: nums = [1,2,3,7], k=8 → trừ chỉ số của 2 và 3 → mảng thành [1,0,0,7] tổng = 8 → True.

Giải thuật

• Đệ quy có nhớ (memoization) với trạng thái (i, total): đang xét phần tử i, tổng hiện tại total.
• Tại mỗi phần tử, thử 3 phép toán: trừ 2*nums[i] (đổi dấu), trừ (i+1), cộng (i+1).
• Nếu đến cuối mảng (i == n) và total == k → True.

Mã ví dụ

size = 100

def is_ok(i, total, k, nums, table):
    n = len(nums)
    if total <= 0:
        return False
    if i >= n:
        if total == k:
            return True
        return False
    if table[i][total] != -1:
        return table[i][total]
    table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
    table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total]
    table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
    return table[i][total]

def solve(nums, k):
    total = sum(nums)
    table = [-1]*size
    for i in range(size):
        table[i] = [-1]*size
    return is_ok(0, total, k, nums, table)

nums = [1,2,3,7]
k = 8
print(solve(nums, k))

Đầu vào

[1,2,3,7], 8

Đầu ra

True