Closest Subsequence Sum


Problem

You are given an integer array numsnums and an integer goalgoal.

You want to choose a subsequence of numsnums such that the sum of its elements is the closest possible to goalgoal. That is, if the sum of the subsequence’s elements is sumsum, then you want to minimize the absolute difference abs(sumgoal)abs(sum - goal).

Return the minimum possible value of abs(sumgoal)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

  • 1nums.length401 \leq nums.length \leq 40
  • 107numsi107-10^7 \leq nums_i \leq 10^7
  • 109goal109-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 n40n \leq 40 is pretty small, I can even get away with O(n4)O(n^4). So I made an array of set ff to maintain all possible sumsum. fif_i holds all sumsum candidates until numsinums_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 nn sets but I don’t think it would AC.

Intuition

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

  • Split numsnums into 2 array, let’s call them leftleft and rightright
  • Calculate all possible sumsum for each sub array. Sort them.
  • For each alefta \in left, find brightb \in right so that a+ba+b is closest to goalgoal. This could be done in O(m×log(m))O(m \times log(m)) with mm being the candidates array length 2n2^n
  • Altogether we have an O(2n×n)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 rightright array.

Complexity

  • Time complexity: O(2n×n)O(2^n \times n)
  • Space complexity: O(2n)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;
    }
};