> For the complete documentation index, see [llms.txt](https://zhenchaogan.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhenchaogan.gitbook.io/leetcode-solution/leetcode-1755-closest-subsequence-sum.md).

# LeetCode 1755. Closest Subsequence Sum

Brute Force + Binary Search + Meet in the Middle

You are given an integer array `nums` and an integer `goal`.

You want to choose a subsequence of `nums` such that the sum of its elements is the closest possible to `goal`. That is, if the sum of the subsequence's elements is `sum`, then you want to **minimize the absolute difference** `abs(sum - goal)`.

Return *the **minimum** possible value of* `abs(sum - goal)`.

Note that a subsequence of an array is an array formed by removing some elements **(possibly all or none)** of the original array.

**Example 1:**

```
Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.
```

**Example 2:**

```
Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.
```

**Example 3:**

```
Input: nums = [1,2,3], goal = -7
Output: 7
```

**Constraints:**

* `1 <= nums.length <= 40`
* `-107 <= nums[i] <= 107`
* `-109 <= goal <= 109`

## Solution:

[English Version in Youtube](https://youtu.be/K_CB32_SQFs)

[中文版解答Youtube Link](https://youtu.be/R_fDIPryG78)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1Fz4y1U7zu/)

```
class Solution {
    
public:
    int maxValue(vector<vector<int>>& events, int k) {
        auto cmp = [](const vector<int>& lhs, const vector<int>& rhs) {
            return lhs[1] < rhs[1];
        };
        sort(events.begin(), events.end(), cmp);
        
        int n = events.size();
        vector<vector<int>> dp(n+1, vector<int>(k+1, 0));
        for (int i = 1; i <= n; i++) {
            int non_overlap_index = 0;
            for (int l = i - 1; l >= 1; l--) {
                if (events[l-1][1] < events[i-1][0]) {
                    non_overlap_index = l;
                    break;
                }
            }
            for (int j = 1; j <= k; j++) {
                dp[i][j] = max(dp[non_overlap_index][j-1] + events[i-1][2], dp[i-1][j]);
            }
        }
        return dp[n][k];
    }
};
```