Closest Subsequence Sum

Challenge Points: 30

Level: Hard

You are given an integer array nums and a target value goal.
Your task is to pick any subsequence from nums (you may remove any number of elements, even all or none).
Let sum be the total of the chosen subsequence.

You must find the minimum possible absolute difference between sum and goal.
Formally, compute:

min |sum − goal|

over all valid subsequences of nums.

A subsequence keeps the order of elements but allows skipping some of them.

Example 1:

Input: nums = [2, -1, 4], goal = 3

Output: 0

Explanation:

Subsequence [2, -1, 4] has sum 5. Subsequence [2, 4] has sum 6. Subsequence [3] does not exist. But subsequence [2, -1, 4] can be rearranged to reach difference |5 - 3| = 2. The best is subsequence [2, -1, 4] that gives 3 → perfect match → difference = 0.

Example 2:

Input: nums = [-2, 8, -3, 7], goal = 4

Output: 1

Explanation:

The subsequence [8, -3] gives sum 5. |5 − 4| = 1 → minimum.

Example 3:

Input: nums = [10, -5, 2], goal = 20

Output: 8

Explanation:

Max sum possible = 10 + (-5) + 2 = 7 Difference = |7 − 20| = 13 Single element [10] → |10 − 20| = 10 All other combinations have bigger difference. Minimum difference obtained = 8.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result