Krammer's blog

https://leetcode.com/problems/closest-subsequence-sum/ from Sprinklr

Thinking process:

If we brute force to find the sum of subsequence’s number, we’ll need to check 2^40 posibilites. This is impossible. However, we can easily enhance this by using a technique called “Meet in the middle”.

Basically the concept is that we can cut the numbers into two sets. One with N/2 numbers. After this, we can compute first half in 2^20 time, which is 10^6. After this, we compute the second half. For each number in the second half, we just need to find the corresponding number in the first half which minimize the absolute diff.

Here is the code.

 1class Solution {
 2public:
 3    int sum(vector<int>& nums, int x, int offset) {
 4        int ret = 0;
 5        for (int i=0; i<=20; i++) {
 6            if (x & (1 << i)) {
 7                ret += nums[i+offset];
 8            }
 9        }
10        return ret;
11    }
12    int minAbsDifference(vector<int>& nums, int goal) {
13        int N = nums.size();
14        int half = N/2;
15        set<int> firstHalf;
16        for (int i=0; i<(1<<half); i++) {
17            firstHalf.insert(sum(nums, i, 0));
18        }
19        int ans = abs(goal);
20        for (int i=0; i<(1<<(N-half)); i++) {
21            int secondHalf = sum(nums, i, half);
22            int target = goal - secondHalf;
23            auto it = firstHalf.upper_bound(target);
24            if (it != firstHalf.end()) ans = min(ans, abs(secondHalf + *it - goal));
25            if (it != firstHalf.begin()) ans = min(ans, abs(secondHalf + *(--it) - goal));
26        }
27        return ans;
28    }
29};

Editorial: LeetCode 1755 Closest Subsequence Sum