Cho mảng nums và giá trị goal. Chọn subsequence của nums sao cho tổng s gần goal nhất (min |s - goal|). Trả về giá trị nhỏ nhất của |s - goal|.
Ví dụ: nums = [8,-8,16,-1], goal = -3 → output = 2 (subsequence [8,-8,-1] sum=-1, |-1-(-3)|=2).
Giải thuật (Meet-in-the-middle + Pruning)
- Sắp xếp nums theo -|x| (giá trị tuyệt đối giảm).
- Precompute neg[i], pos[i] = tổng âm/dương từ i đến cuối.
- Duyệt i=0..n-1, duy trì set s các tổng có thể đạt được.
- Pruning: chỉ giữ x trong s nếu [x+neg[i], x+pos[i]] giao với [goal-ans, goal+ans].
- Cập nhật ans = min(ans, |x+nums[i]-goal|).
Code Python
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
Đầu vào / Đầu ra
Input: [8,-8,16,-1], -3
Output: 2