โปรแกรมหา Subsequence Sum ใกล้เคียง Target มากที่สุดใน Python

ปัญหา

อาร์เรย์ nums และ Target Goal เลือก Subsequence ให้ Sum ใกล้ Goal มากที่สุด (Minimize |Sum - Goal|)

ตัวอย่าง

nums = [8,-8,16,-1], goal = -3 → Output: 2

Subsequence [8,-8,-1] Sum = -1, |(-1) - (-3)| = 2

อัลกอริทึม (Meet-in-the-Middle + Pruning)

1. Sort nums ตาม |Value| Descending (ค่าสำคัญก่อน)
2. Precompute Suffix Sums: Neg[i] = Sum of Negative จาก i ถึง End, Pos[i] = Sum of Positive
3. DP Set: เก็บ Possible Sums ที่เป็นไปได้จนถึง Index i
4. Pruning: ถ้า Range [Current+Neg[i], Current+Pos[i]] ไม่ทับกับ [Goal-Ans, Goal+Ans] → Skip
5. Update Answer เมื่อเจา Sum ใกล้ Goal กว่า

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

from collections import Counter

def solve(nums, goal):
    n = len(nums)
    nums.sort(key=lambda x: -abs(x))
    neg = [0] * (n + 1)
    pos = [0] * (n + 1)
    
    for i in range(n - 1, -1, -1):
        if nums[i] < 0:
            neg[i] = neg[i + 1] + nums[i]
            pos[i] = pos[i + 1]
        else:
            pos[i] = pos[i + 1] + nums[i]
            neg[i] = neg[i + 1]
    
    ans = abs(goal)
    s = {0}
    
    def check(a, b):
        return not (b < goal - ans or goal + ans < a)
    
    for i in range(n):
        sl = [x for x in s if check(x + neg[i], x + pos[i])]
        if not sl:
            break
        s = set(sl)
        for x in sl:
            y = x + nums[i]
            if abs(y - goal) < ans:
                ans = abs(y - goal)
            if ans == 0:
                return 0
            s.add(y)
    return ans

nums = [8, -8, 16, -1]
goal = -3
print(solve(nums, goal))  # 2

ความซับซ้อน

• Time: O(n × |States|) Pruning ลด State มาก
• Space: O(|States|)
• เหมาะกับ n ≤ 40-50