Closest Subsequence Sum


Problem

You are given an integer array and an integer .

You want to choose a subsequence of such that the sum of its elements is the closest possible to . That is, if the sum of the subsequence's elements is , then you want to minimize the absolute difference .

Return the minimum possible value of .

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

Submit your solution at here

Solution

Full search brute force (TLE)

First idea come to my mind is Brute Force because is pretty small, I can even get away with . So I made an array of set to maintain all possible . holds all candidates until . 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 sets but I don't think it would AC.

Intuition

So I changed my approach, notice that so would very likely to TLE, but how about ? Seems sensible. The idea is simple:

  • Split into 2 array, let's call them and
  • Calculate all possible for each sub array. Sort them.
  • For each , find so that is closest to . This could be done in with being the candidates array length
  • Altogether we have an solution. It gives AC but I was afraid it is still slow I made a small optimization to reduce search range while traversing array.

Complexity

  • Time complexity:
  • Space complexity:

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;
    }
};