We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Closest Subsequence Sum

Number: 1881

Difficulty: Hard

Paid? No

Companies: Uber, Sprinklr

Problem Description

Given an integer array nums and an integer goal, we want to choose a subsequence (i.e., any subset of elements, including possibly none or all) such that the absolute difference between the sum of the subsequence and goal is minimized. Return this minimum possible absolute difference.

Key Insights

  • The array length can be up to 40, making the total number of subsequences (2^n) too large for direct enumeration.
  • Use meet-in-the-middle: split the array into two halves and generate all possible sums for each half.
  • Sort one half’s sums (e.g., the right half) to enable efficient binary search.
  • For each sum in the left half, use binary search in the right half to find a complementary sum that minimizes the difference with goal.
  • The empty subsequence (sum = 0) is naturally included in the generated sums.

Space and Time Complexity

Time Complexity: O(2^(n/2) * log(2^(n/2)))
Space Complexity: O(2^(n/2)) for storing the subset sums from each half

Solution

We split the given nums array into two halves. For each half, we generate all possible subset sums — this is feasible because each half has at most 20 elements (2^20 possible sums). One of the lists (rightSums) is sorted to allow binary search. For each sum in leftSums, we compute the remainder (goal - leftSum) and perform binary search in rightSums to find the candidate sums closest to this remainder. We update the result with the minimum absolute difference found between (leftSum + rightCandidate) and goal. This approach effectively reduces the exponential factor by splitting the problem and leveraging efficient search.

Code Solutions

def closestSubsequenceSum(nums, goal):
    # Helper function to generate all subset sums of a given list.
    def gen_sums(arr):
        sums = [0]
        # For every number, add it to all existing sums to build new sums.
        for num in arr:
            new_sums = [s + num for s in sums]
            sums += new_sums
        return sums

    n = len(nums)
    mid = n // 2
    left = nums[:mid]
    right = nums[mid:]
    
    # Generate all possible subset sums for left and right halves.
    left_sums = gen_sums(left)
    right_sums = gen_sums(right)
    
    # Sort right_sums for binary search.
    right_sums.sort()
    
    res = float('inf')
    import bisect
    for s in left_sums:
        remain = goal - s
        # Find the insertion point to keep right_sums sorted.
        idx = bisect.bisect_left(right_sums, remain)
        # Check the candidate at the insertion point.
        if idx < len(right_sums):
            res = min(res, abs(s + right_sums[idx] - goal))
        # Check the candidate just before the insertion point.
        if idx > 0:
            res = min(res, abs(s + right_sums[idx - 1] - goal))
        if res == 0:
            return 0
    return res

# Example usage
print(closestSubsequenceSum([5, -7, 3, 5], 6))  # Expected output: 0
← Back to All Questions