#1755

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Closest Subsequence Sum

Find the minimum absolute difference between a target goal and any subsequence sum using optimized dynamic programming and bit manipulation.

array two pointers dynamic programming bit manipulation sorting

Problem Statement

You are given an integer array nums and an integer goal. Your task is to select any subsequence of nums so that the sum of the chosen elements is as close as possible to goal.

Return the smallest possible absolute difference between the sum of a subsequence and the target goal. For example, if the subsequence sum is sum, you must minimize abs(sum - goal). Arrays can contain negative numbers, and subsequences may be empty.

Examples

Example 1

Input: nums = [5,-7,3,5], goal = 6

Output: 0

Choose the whole array as a subsequence, with a sum of 6. This is equal to the goal, so the absolute difference is 0.

Example 2

Input: nums = [7,-9,15,-2], goal = -5

Output: 1

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.

Example 3

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

Output: 7

Example details omitted.

Constraints

1 <= nums.length <= 40
-107 <= nums[i] <= 107
-109 <= goal <= 109

Solution Approach

Meet-in-the-Middle Subsequence Sum

Split nums into two halves, generate all possible subsequence sums for each half using bitmasking, and store them in sorted arrays. This reduces the problem from 2^n to 2^(n/2) and prepares for efficient merging.

Binary Search to Minimize Difference

For each sum in the first half, use binary search on the second half's sorted sums to find the closest total sum to the goal. Track the minimum absolute difference encountered during this search.

State Transition Dynamic Programming Alternative

Use DP to record all reachable sums up to the length of the array. Iterate through nums, updating a set of achievable sums by adding each number to previous sums. Finally, compute the minimum absolute difference to the goal from the set.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The meet-in-the-middle approach reduces the time complexity to O(2^(n/2) log 2^(n/2)) = O(2^(n/2) * n) due to sorting and binary search. Space complexity is O(2^(n/2)) for storing subsequence sums. DP alternatives can have O(n * sum_range) time and space, which may exceed constraints for large numbers.

What Interviewers Usually Probe

Checks if you understand subset sum state transitions and meet-in-the-middle optimization.
Tests your ability to reduce exponential time via splitting and sorting sums.
Looks for correct handling of negative numbers and empty subsequences.

Common Pitfalls or Variants

Common pitfalls

Attempting a full 2^n enumeration without splitting causes timeouts for n > 20.
Failing to sort one half's sums prevents efficient binary search and correct minimum difference calculation.
Overlooking empty subsequences or negative numbers can result in incorrect absolute difference computation.

Follow-up variants

Find the closest subsequence sum constrained to at most k elements.
Compute closest subsequence sum where elements must be consecutive in nums.
Determine closest subsequence product instead of sum, emphasizing DP state tracking.

FAQ

What is the main challenge in Closest Subsequence Sum?

The challenge is efficiently finding a subsequence sum closest to goal without enumerating all 2^n possibilities.

Why use meet-in-the-middle for this problem?

Splitting the array halves reduces time complexity from O(2^n) to O(2^(n/2) log 2^(n/2)), making large inputs feasible.

Can dynamic programming alone solve Closest Subsequence Sum?

Yes, DP can track all reachable sums, but naive DP may exceed memory limits for large absolute values.

How do negative numbers affect the solution?

Negative numbers expand possible sums in both directions, so proper handling ensures the minimum absolute difference is correct.

Does GhostInterview explain state transition dynamic programming for this problem?

Yes, it guides you to implement DP and combine it with meet-in-the-middle and binary search to compute the minimal difference efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        left = set()
        right = set()

        self.getSubSeqSum(0, 0, nums[: n // 2], left)
        self.getSubSeqSum(0, 0, nums[n // 2 :], right)

        result = inf
        right = sorted(right)
        rl = len(right)

        for l in left:
            remaining = goal - l
            idx = bisect_left(right, remaining)

            if idx < rl:
                result = min(result, abs(remaining - right[idx]))

            if idx > 0:
                result = min(result, abs(remaining - right[idx - 1]))

        return result

    def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]):
        if i == len(arr):
            result.add(curr)
            return

        self.getSubSeqSum(i + 1, curr, arr, result)
        self.getSubSeqSum(i + 1, curr + arr[i], arr, result)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        left = set()
        right = set()

        self.getSubSeqSum(0, 0, nums[: n // 2], left)
        self.getSubSeqSum(0, 0, nums[n // 2 :], right)

        result = inf
        right = sorted(right)
        rl = len(right)

        for l in left:
            remaining = goal - l
            idx = bisect_left(right, remaining)

            if idx < rl:
                result = min(result, abs(remaining - right[idx]))

            if idx > 0:
                result = min(result, abs(remaining - right[idx - 1]))

        return result

    def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]):
        if i == len(arr):
            result.add(curr)
            return

        self.getSubSeqSum(i + 1, curr, arr, result)
        self.getSubSeqSum(i + 1, curr + arr[i], arr, result)

Continue Practicing

#2035 partition array into two arrays to minimize sum difference #1799 maximize score after n operations #1994 the number of good subsets