ตรวจสอบว่าผลรวมอาร์เรย์ทำให้เป็น K ได้ด้วย 3 การดำเนินการ ใน Python

ปัญหา

ให้อาร์เรย์ nums และเป้าหมาย K สามารถทำกับแต่ละสมาชิก ได้เพียง 1 ครั้ง:

1. ทำให้เป็นลบ (คูณ -1)
2. บวกดัชนี (1-based)
3. ลบดัชนี (1-based)

ตัวอย่าง

nums = [1,2,3,7], K = 8
ลบดัชนีของ 2,3: [1, 2-2, 3-3, 7] = [1,0,0,7] → sum=8 → True

แนวคิด (Dynamic Programming)

DP[i][sum] = สามารถทำได้หรือไม่จนถึง index i ผลรวม = sum
State transition: ลอง 3 ทางเลือก + ไม่ทำอะไร

โค้ดตัวอย่าง

def solve(nums, K):
    n = len(nums)
    total = sum(nums)
    # offset เพื่อจัดการ index ลบ
    offset = 10000
    max_sum = 20000
    dp = [[False]*(max_sum+1) for _ in range(n+1)]
    dp[0][total + offset] = True
    
    for i in range(n):
        for s in range(max_sum+1):
            if not dp[i][s]:
                continue
            val = nums[i]
            idx = i + 1
            # 1. ไม่ทำอะไร
            dp[i+1][s] = True
            # 2. ทำให้เป็นลบ
            dp[i+1][s - 2*val] = True
            # 3. บวกดัชนี
            dp[i+1][s + idx] = True
            # 4. ลบดัชนี
            dp[i+1][s - idx] = True
    
    return dp[n][K + offset]

print(solve([1,2,3,7], 8))  # True

อินพุต / เอาต์พุต

Input:  [1,2,3,7], 8
Output: True