Closest Subsequence Sum

Problem

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

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.

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.

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

Constraints

• $1 \leq nums.length \leq 40$
• $-10^7 \leq nums_i \leq 10^7$
• $-10^9 \leq goal \leq 10^9$

Submit your solution at here

Solution

Full search brute force (TLE)

First idea come to my mind is Brute Force because $n \leq 40$ is pretty small, I can even get away with $O(n^4)$. So I made an array of set $f$ to maintain all possible $sum$. $f_i$ holds all $sum$ candidates until $nums_i$. Here is the code for your reference

class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<set<int>> f(n+1);
        f[0].insert(0);
        int ret = abs(goal);
        for(int i = 1;i<=n;i++) {
            for(auto x: f[i-1]) {
                int score;
                f[i].insert(x);
                score = abs(nums[i-1] - goal);
                if(score < ret || nums[i-1] < goal) {
                    ret = min(ret, score);
                    f[i].insert(nums[i-1]);
                }
                auto sum = x + nums[i-1];
                score = abs(sum - goal);
                if(score < ret || sum < goal) {
                    ret = min(ret, score);
                    f[i].insert(sum);
                }
            }
        }
        return ret;
    }
};

Sadly this gives TLE, I can optimize it further by using only 1 sets instead of $n$ sets but I don’t think it would AC.

Intuition

So I changed my approach, notice that $n = 40$ so $O(2^n) = T(2^{40})$ would very likely to TLE, but how about $T(2^{20})$? Seems sensible. The idea is simple:

• Split $nums$ into 2 array, let’s call them $left$ and $right$
• Calculate all possible $sum$ for each sub array. Sort them.
• For each $a \in left$, find $b \in right$ so that $a+b$ is closest to $goal$. This could be done in $O(m \times log(m))$ with $m$ being the candidates array length $2^n$
• Altogether we have an $O(2^n \times n)$ solution. It gives AC but I was afraid it is still slow I made a small optimization to reduce search range while traversing $right$ array.

Complexity

• Time complexity: $O(2^n \times n)$
• Space complexity: $O(2^n)$

Code

class Solution {
public:
    void buildPermutation(vector<int>& nums, vector<int>& a, int i, int n) {
        int k = n-i;
        int size = (1<<k);
        a.resize(size,0);
        for(int j = 0;j<size;j++) {
            for(int b = 0;b<k;b++) {
                if((1<<b)&j) {
                    continue;
                }
                int next = (1<<b)|j;
                a[next] += nums[i+b];
            }
        }
        sort(a.begin(), a.end());
    }
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size();
        int m = n/2;
        vector<int> left, right;
        buildPermutation(nums, left, 0, m);
        buildPermutation(nums, right, m, n);
        int ret = 2e9+1;
        int j = right.size();
        for(auto a: left) {
            int target = goal - a;
            j = distance(right.begin(), lower_bound(right.begin(), right.begin()+j, target));
            if(j < right.size()) {
                int b = right[j];
                ret = min(ret, abs(a + b - goal));
            }
            if(j != 0) {
                int b = right[j-1];
                ret = min(ret, abs(a + b - goal));
            }
            if(ret == 0) {
                break;
            }
        }
        return ret;
    }
};