Closest Subsequence Sum (LeetCode 1755)
Report the smallest distance abs(sum - goal) you can reach, where sum is the total of some subsequence of nums.
A subsequence keeps any of the numbers of nums, in their order, and drops the rest. It may keep every number or none of them; keeping none gives the sum 0. Only the total matters here, so any set of positions of nums counts as one choice.
Worked Examples
nums = [5,-7,3,5], goal = 60goal.nums = [7,-9,15,-2], goal = -51nums = [1,2,3], goal = -77⚖️Formal Constraints & Bounds
1 <= nums.length <= 40-107 <= nums[i] <= 107-109 <= goal <= 109
Core Insight
Every subsequence is one choice from the left half plus one from the right half, so two lists of 2^(n/2) subset sums replace 2^n subsequences: for each left sum, the partner that brings the total closest to goal sits next to goal - s in the sorted right list, on one side or the other.
Real-World Scenario & Production Applications
Picking the items whose total lands as close as possible to a target, such as the jobs that best fill a machine's time slot, or the line items that come closest to an invoice total, is this search. With a few dozen items and large values, splitting the items into two groups and joining the two lists of totals is what makes an exact answer affordable.
Step-by-Step Execution Trace Table
Example 2, nums = [7,-9,15,-2], goal = -5. half = 2, so left = all_sums([7, -9]) = [0, 7, -9, -2] and right = sorted(all_sums([15, -2])) = [-2, 0, 13, 15]; best starts at abs(-5) = 5:
| Step | s | need = goal - s | k | right[k] - need | need - right[k - 1] | best |
|---|---|---|---|---|---|---|
| 1 | 0 | -5 | 0 | -2 - (-5) = 3 | none (k = 0) | 3 |
| 2 | 7 | -12 | 0 | -2 - (-12) = 10 | none (k = 0) | 3 |
| 3 | -9 | 4 | 2 | 13 - 4 = 9 | 4 - 0 = 4 | 3 |
| 4 | -2 | -3 | 0 | -2 - (-3) = 1 | none (k = 0) | 1 |
| End | 1 |
Step 4 pairs the left choice [7, -9] (sum -2) with the right choice [-2]: -4 in all, 1 away from -5. Here the sum just below need never wins, but on nums = [2, 9, 1, 8], goal = 13 it decides the answer: for s = 11, need = 2 and the sorted right sums are [0, 1, 8, 9], so right[k] = 8 is 6 away while right[k - 1] = 1 is 1 away (total 12). Checking only right[k] returns 4 there instead of 1.
nums = [5,-7,3,5], goal = 6Expected:0| 1 | Split `nums` into two halves and list every subset sum of each half, including the empty choice. |
| 2 | Sort one list; for each sum `s` of the other, the partner that brings `s + r` closest to `goal` is the sorted sum nearest `need = goal - s`. |
| 3 | The shape: a helper that lists one half's sums, two calls on the two halves, one sort, then one loop over the left sums with a binary search in the right list and a running minimum. |
| 4 | Return the running minimum: the smallest distance any left-plus-right pair reached. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
With 40 numbers there are 2^40, about a trillion, subsequences: far too many to try. Meet in the Middle splits the numbers into two halves of 20. Each half has only 2^20, about a million, choices, so you can list every subset sum of each half. Any subsequence of the whole array is one choice from the left half plus one from the right half, so the question becomes: which left sum s and right sum r make s + r closest to goal? For a fixed s, the best r is the one closest to need = goal - s, and a sorted right finds it with one binary search.
🧗 The Analogy: Two Climbers Meeting on a Ridge
Two climbers start from opposite ends of a long ridge instead of one climber walking all of it. Each covers only half the distance, and they only have to agree on where they meet. Here each half explores its own choices, and the join step is where they meet: for every left sum, the right half offers the sum that completes it best.
🔑 Why It Works
Two lists of 2^(n/2) sums replace one list of 2^n. Sorting one of them lets every left sum find its partner in about n steps, and checking the neighbour on each side of need makes sure the closest partner is never missed.
Checking only the sum at or above
need:bisect_left(right, need)gives the insertion pointk; the closest right sum isright[k]orright[k - 1]. Withoutright[k - 1],[2, 9, 1, 8]withgoal = 13returns 4 instead of 1.Leaving out the empty choice:
all_sumsstarts fromsums = [0]. Listing only non-empty choices loses every answer that uses one half alone:[-4, 6]withgoal = 6returns 4 instead of 0.Dropping a number at the split: the halves are
nums[:half]andnums[half:];nums[half + 1:]never usesnums[half].Searching an unsorted list: sort
rightonce before the loop.bisect_leftassumes a sorted list, and on the orderall_sumsbuilds it finds the wrong neighbours.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The total of some subsequence of nums" and "the smallest distance abs(sum - goal)", with 1 <= nums.length <= 40 and values up to 10^7: a subset search whose 2^40 choices are far too many, with sums too spread out for a table over them. Two halves of 20 numbers have about a million subset sums each: that is the signal for Meet in the Middle.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
left and right hold every subset sum of their half, the empty choice included, and right is sorted. Every subsequence is s + r for one s in left and one r in right, so for each s the best r sits next to k = bisect_left(right, need) with need = goal - s: right[k] from above or right[k - 1] from below. best is the smallest abs(s + r - goal) seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Starting
bestat 0 or at a made-up bound: start from a real distance,abs(goal)for choosing nothing. Withgoalfar from every reachable sum, abestof 0 is returned as if some subsequence hitgoalexactly.A single number:
halfis 0, soleftis just[0]andrightholds both choices of that number. Code that assumes two non-empty halves breaks onnums = [7].Building the sums with one recursive call per sum: at N = 40 that is about two million Python calls; the list doubling in
all_sumsdoes the same work in a few list operations per number.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Meet in the Middle. With up to forty numbers, trying every subsequence means two to the forty, about a trillion sums, so I split the array into two halves of twenty and list every subset sum of each half, about a million each. I start each list from zero, so a half can also contribute nothing. Every subsequence is one left sum plus one right sum. I sort the right list once, and for each left sum s I look for the right sum closest to need, which is goal minus s. A binary search gives the insertion point k, and the closest value is right of k, just above need, or right of k minus one, just below it. Checking both is the trap I avoid, because the answer can come from below. That's O of two to the N over two, times N, time and O of two to the N over two space.
Complexity & Mathematical Proof
O(2^(N/2) * N)
Look at the code: all_sums doubles its list once per number, so a half of N/2 numbers ends with 2^(N/2) sums, and building them costs 1 + 2 + 4 + ... + 2^(N/2 - 1) < 2^(N/2) additions: O(2^(N/2)) for both halves. sorted on the 2^(N/2) right sums costs O(2^(N/2) * log 2^(N/2)) = O(2^(N/2) * N). The loop runs once per left sum, 2^(N/2) times, and its bisect_left searches 2^(N/2) sorted values in O(log 2^(N/2)) = O(N) steps; the rest of the body is O(1). Total: O(2^(N/2) * N).
O(2^(N/2))
left and right hold at most 2^(N/2) + 2^(N/2) sums (the halves differ by at most one number), and the slices nums[:half] and nums[half:] hold N numbers. The answer is one integer, and nothing recurses.
Derivation Progression
sums += [s + x for s in sums] doubles the list for each of the N/2 numbers of a half; the additions sum to fewer than 2^(N/2) per half.
sorted on 2^(N/2) values costs 2^(N/2) * log 2^(N/2) = 2^(N/2) * N/2 comparisons.
2^{N/2} iterations
for s in left visits every left sum once.
O(N)
bisect_left(right, need) halves a range of 2^(N/2) values, about N/2 steps; the two neighbour checks are O(1).
The sort and the loop dominate. At N = 40 that is about 2 * 10^7 steps instead of 2^40, about 10^12, sums for the brute force.
Variable Definitions
Length of nums, the number of numbers to choose from
Number of subset sums of one half: every number of the half is kept or dropped
Memory Architecture & Bounds
O(1): all_sums is called twice and never recurses
O(2^(N/2)): the lists left and right
O(1): one integer
Boundary Best / Worst Cases
: both lists are always built in full, and every left sum is searched
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the total of some subsequence of nums", "the smallest distance abs(sum - goal)", and 1 <= nums.length <= 40 with values up to . A subset search too big for and too spread out for a table over sums: Meet in the Middle, one list of subset sums per half.
: subsequences are out of reach, but each half has subset sums. Sums lie between and and the distance to goal stays below , inside a 32-bit integer; a table over that range of sums would need cells.
At N = 40 each list holds about a million Python integers, tens of megabytes: build them with list operations, not one Python call per sum, and in a language with fixed-size integers keep the sums in 64-bit values if the value range can grow. Both lists can also be sorted and walked with two pointers, one from each end, which replaces the binary searches with one linear pass.
Closest Subsequence Sum (LeetCode 1755)
Report the smallest distance abs(sum - goal) you can reach, where sum is the total of some subsequence of nums.
A subsequence keeps any of the numbers of nums, in their order, and drops the rest. It may keep every number or none of them; keeping none gives the sum 0. Only the total matters here, so any set of positions of nums counts as one choice.
Worked Examples
nums = [5,-7,3,5], goal = 60goal.nums = [7,-9,15,-2], goal = -51nums = [1,2,3], goal = -77⚖️Formal Constraints & Bounds
1 <= nums.length <= 40-107 <= nums[i] <= 107-109 <= goal <= 109
Core Insight
Every subsequence is one choice from the left half plus one from the right half, so two lists of 2^(n/2) subset sums replace 2^n subsequences: for each left sum, the partner that brings the total closest to goal sits next to goal - s in the sorted right list, on one side or the other.
Real-World Scenario & Production Applications
Picking the items whose total lands as close as possible to a target, such as the jobs that best fill a machine's time slot, or the line items that come closest to an invoice total, is this search. With a few dozen items and large values, splitting the items into two groups and joining the two lists of totals is what makes an exact answer affordable.
Step-by-Step Execution Trace Table
Example 2, nums = [7,-9,15,-2], goal = -5. half = 2, so left = all_sums([7, -9]) = [0, 7, -9, -2] and right = sorted(all_sums([15, -2])) = [-2, 0, 13, 15]; best starts at abs(-5) = 5:
| Step | s | need = goal - s | k | right[k] - need | need - right[k - 1] | best |
|---|---|---|---|---|---|---|
| 1 | 0 | -5 | 0 | -2 - (-5) = 3 | none (k = 0) | 3 |
| 2 | 7 | -12 | 0 | -2 - (-12) = 10 | none (k = 0) | 3 |
| 3 | -9 | 4 | 2 | 13 - 4 = 9 | 4 - 0 = 4 | 3 |
| 4 | -2 | -3 | 0 | -2 - (-3) = 1 | none (k = 0) | 1 |
| End | 1 |
Step 4 pairs the left choice [7, -9] (sum -2) with the right choice [-2]: -4 in all, 1 away from -5. Here the sum just below need never wins, but on nums = [2, 9, 1, 8], goal = 13 it decides the answer: for s = 11, need = 2 and the sorted right sums are [0, 1, 8, 9], so right[k] = 8 is 6 away while right[k - 1] = 1 is 1 away (total 12). Checking only right[k] returns 4 there instead of 1.
nums = [5,-7,3,5], goal = 6Expected:0| 1 | Split `nums` into two halves and list every subset sum of each half, including the empty choice. |
| 2 | Sort one list; for each sum `s` of the other, the partner that brings `s + r` closest to `goal` is the sorted sum nearest `need = goal - s`. |
| 3 | The shape: a helper that lists one half's sums, two calls on the two halves, one sort, then one loop over the left sums with a binary search in the right list and a running minimum. |
| 4 | Return the running minimum: the smallest distance any left-plus-right pair reached. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
With 40 numbers there are 2^40, about a trillion, subsequences: far too many to try. Meet in the Middle splits the numbers into two halves of 20. Each half has only 2^20, about a million, choices, so you can list every subset sum of each half. Any subsequence of the whole array is one choice from the left half plus one from the right half, so the question becomes: which left sum s and right sum r make s + r closest to goal? For a fixed s, the best r is the one closest to need = goal - s, and a sorted right finds it with one binary search.
🧗 The Analogy: Two Climbers Meeting on a Ridge
Two climbers start from opposite ends of a long ridge instead of one climber walking all of it. Each covers only half the distance, and they only have to agree on where they meet. Here each half explores its own choices, and the join step is where they meet: for every left sum, the right half offers the sum that completes it best.
🔑 Why It Works
Two lists of 2^(n/2) sums replace one list of 2^n. Sorting one of them lets every left sum find its partner in about n steps, and checking the neighbour on each side of need makes sure the closest partner is never missed.
Checking only the sum at or above
need:bisect_left(right, need)gives the insertion pointk; the closest right sum isright[k]orright[k - 1]. Withoutright[k - 1],[2, 9, 1, 8]withgoal = 13returns 4 instead of 1.Leaving out the empty choice:
all_sumsstarts fromsums = [0]. Listing only non-empty choices loses every answer that uses one half alone:[-4, 6]withgoal = 6returns 4 instead of 0.Dropping a number at the split: the halves are
nums[:half]andnums[half:];nums[half + 1:]never usesnums[half].Searching an unsorted list: sort
rightonce before the loop.bisect_leftassumes a sorted list, and on the orderall_sumsbuilds it finds the wrong neighbours.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The total of some subsequence of nums" and "the smallest distance abs(sum - goal)", with 1 <= nums.length <= 40 and values up to 10^7: a subset search whose 2^40 choices are far too many, with sums too spread out for a table over them. Two halves of 20 numbers have about a million subset sums each: that is the signal for Meet in the Middle.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
left and right hold every subset sum of their half, the empty choice included, and right is sorted. Every subsequence is s + r for one s in left and one r in right, so for each s the best r sits next to k = bisect_left(right, need) with need = goal - s: right[k] from above or right[k - 1] from below. best is the smallest abs(s + r - goal) seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Starting
bestat 0 or at a made-up bound: start from a real distance,abs(goal)for choosing nothing. Withgoalfar from every reachable sum, abestof 0 is returned as if some subsequence hitgoalexactly.A single number:
halfis 0, soleftis just[0]andrightholds both choices of that number. Code that assumes two non-empty halves breaks onnums = [7].Building the sums with one recursive call per sum: at N = 40 that is about two million Python calls; the list doubling in
all_sumsdoes the same work in a few list operations per number.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Meet in the Middle. With up to forty numbers, trying every subsequence means two to the forty, about a trillion sums, so I split the array into two halves of twenty and list every subset sum of each half, about a million each. I start each list from zero, so a half can also contribute nothing. Every subsequence is one left sum plus one right sum. I sort the right list once, and for each left sum s I look for the right sum closest to need, which is goal minus s. A binary search gives the insertion point k, and the closest value is right of k, just above need, or right of k minus one, just below it. Checking both is the trap I avoid, because the answer can come from below. That's O of two to the N over two, times N, time and O of two to the N over two space.
Complexity & Mathematical Proof
O(2^(N/2) * N)
Look at the code: all_sums doubles its list once per number, so a half of N/2 numbers ends with 2^(N/2) sums, and building them costs 1 + 2 + 4 + ... + 2^(N/2 - 1) < 2^(N/2) additions: O(2^(N/2)) for both halves. sorted on the 2^(N/2) right sums costs O(2^(N/2) * log 2^(N/2)) = O(2^(N/2) * N). The loop runs once per left sum, 2^(N/2) times, and its bisect_left searches 2^(N/2) sorted values in O(log 2^(N/2)) = O(N) steps; the rest of the body is O(1). Total: O(2^(N/2) * N).
O(2^(N/2))
left and right hold at most 2^(N/2) + 2^(N/2) sums (the halves differ by at most one number), and the slices nums[:half] and nums[half:] hold N numbers. The answer is one integer, and nothing recurses.
Derivation Progression
sums += [s + x for s in sums] doubles the list for each of the N/2 numbers of a half; the additions sum to fewer than 2^(N/2) per half.
sorted on 2^(N/2) values costs 2^(N/2) * log 2^(N/2) = 2^(N/2) * N/2 comparisons.
2^{N/2} iterations
for s in left visits every left sum once.
O(N)
bisect_left(right, need) halves a range of 2^(N/2) values, about N/2 steps; the two neighbour checks are O(1).
The sort and the loop dominate. At N = 40 that is about 2 * 10^7 steps instead of 2^40, about 10^12, sums for the brute force.
Variable Definitions
Length of nums, the number of numbers to choose from
Number of subset sums of one half: every number of the half is kept or dropped
Memory Architecture & Bounds
O(1): all_sums is called twice and never recurses
O(2^(N/2)): the lists left and right
O(1): one integer
Boundary Best / Worst Cases
: both lists are always built in full, and every left sum is searched
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the total of some subsequence of nums", "the smallest distance abs(sum - goal)", and 1 <= nums.length <= 40 with values up to . A subset search too big for and too spread out for a table over sums: Meet in the Middle, one list of subset sums per half.
: subsequences are out of reach, but each half has subset sums. Sums lie between and and the distance to goal stays below , inside a 32-bit integer; a table over that range of sums would need cells.
At N = 40 each list holds about a million Python integers, tens of megabytes: build them with list operations, not one Python call per sum, and in a language with fixed-size integers keep the sums in 64-bit values if the value range can grow. Both lists can also be sorted and walked with two pointers, one from each end, which replaces the binary searches with one linear pass.