Closest Subsequence Sum (LeetCode 1755)
You will see how listing the subset sums of each half and joining them with one binary search per left sum answers a question about 2^40 subsequences.
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 = 60nums = [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
Why It Works & Core Invariant
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. |
Target: Closest Subsequence Sum (LeetCode 1755). Each new number doubles the list: every old sum stays (the number is skipped) and comes back with the number added. Starting from `[0]` keeps the choice that takes nothing from this half.
Branch exploration via in-place mutation followed by immediate backtrack restoration. Sibling deduplication prunes duplicate subtrees.
Recursive base case: if len(path) == target: record copy; for i in range(start, n): choose, recurse, un-choose.
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.
🪄 The Mathematical Harmony / Magic Trick
left = all_sums(nums[:half])right = sorted(all_sums(nums[half:]))for s in left: need = goal - s k = bisect_left(right, need) if k < len(right): best = min(best, right[k] - need) if k > 0: best = min(best, need - right[k - 1]) 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.
💡 Summary
Split the array, list every subset sum of each half (the empty choice included), sort the right list, and for each left sum check the right sums just above and just below goal - s. time and space.
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
You will see how a senior engineer spots a subset search that is too big for 2^n and too spread out for a table over sums, and splits it in half.
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
Check both neighbours:
right[k] - needwhenk < len(right)andneed - right[k - 1]whenk > 0. The closest sum can sit just belowneed; withoutright[k - 1],[2, 9, 1, 8]withgoal = 13returns 4 instead of 1.sums = [0]inall_sums: the empty choice is what lets an answer use one half alone ([-4, 6]withgoal = 6needs[6]by itself).nums[:half]andnums[half:]: every number in exactly one half. Slicingnums[half + 1:]dropsnums[half].right = sorted(...)before the loop:bisect_lefton the unsorted orderall_sumsbuilds finds the wrong neighbours.
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.
So: list every subset sum of each half (from [0]), sort right, and for each s in left check right[k] and right[k - 1] around need = goal - s.
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.
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).
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.
Checking only right[k] misses sums just below need ([2, 9, 1, 8], goal = 13 must return 1). 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.
Core Algorithmic State Invariants
`all_sums` starts from `[0]` and doubles its list with each number, so `left` and `right` hold every subset sum of their half, the empty choice included. Every subsequence of `nums` is one left sum plus one right sum.
For a left sum `s`, the best partner is the right sum closest to `need = goal - s`. In the sorted `right` it is `right[k]` or `right[k - 1]` with `k = bisect_left(right, need)`; checking only `right[k]` misses answers from below.
Two lists of 2^(N/2) sums, one sort and one binary search per left sum: O(2^(N/2) * N) time and O(2^(N/2)) space, about 2 * 10^7 steps at N = 40 instead of 2^40 sums.
Closest Subsequence Sum (LeetCode 1755)
You will see how listing the subset sums of each half and joining them with one binary search per left sum answers a question about 2^40 subsequences.
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 = 60nums = [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
Why It Works & Core Invariant
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. |
Target: Closest Subsequence Sum (LeetCode 1755). Each new number doubles the list: every old sum stays (the number is skipped) and comes back with the number added. Starting from `[0]` keeps the choice that takes nothing from this half.
Branch exploration via in-place mutation followed by immediate backtrack restoration. Sibling deduplication prunes duplicate subtrees.
Recursive base case: if len(path) == target: record copy; for i in range(start, n): choose, recurse, un-choose.
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.
🪄 The Mathematical Harmony / Magic Trick
left = all_sums(nums[:half])right = sorted(all_sums(nums[half:]))for s in left: need = goal - s k = bisect_left(right, need) if k < len(right): best = min(best, right[k] - need) if k > 0: best = min(best, need - right[k - 1]) 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.
💡 Summary
Split the array, list every subset sum of each half (the empty choice included), sort the right list, and for each left sum check the right sums just above and just below goal - s. time and space.
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
You will see how a senior engineer spots a subset search that is too big for 2^n and too spread out for a table over sums, and splits it in half.
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
Check both neighbours:
right[k] - needwhenk < len(right)andneed - right[k - 1]whenk > 0. The closest sum can sit just belowneed; withoutright[k - 1],[2, 9, 1, 8]withgoal = 13returns 4 instead of 1.sums = [0]inall_sums: the empty choice is what lets an answer use one half alone ([-4, 6]withgoal = 6needs[6]by itself).nums[:half]andnums[half:]: every number in exactly one half. Slicingnums[half + 1:]dropsnums[half].right = sorted(...)before the loop:bisect_lefton the unsorted orderall_sumsbuilds finds the wrong neighbours.
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.
So: list every subset sum of each half (from [0]), sort right, and for each s in left check right[k] and right[k - 1] around need = goal - s.
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.
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).
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.
Checking only right[k] misses sums just below need ([2, 9, 1, 8], goal = 13 must return 1). 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.
Core Algorithmic State Invariants
`all_sums` starts from `[0]` and doubles its list with each number, so `left` and `right` hold every subset sum of their half, the empty choice included. Every subsequence of `nums` is one left sum plus one right sum.
For a left sum `s`, the best partner is the right sum closest to `need = goal - s`. In the sorted `right` it is `right[k]` or `right[k - 1]` with `k = bisect_left(right, need)`; checking only `right[k]` misses answers from below.
Two lists of 2^(N/2) sums, one sort and one binary search per left sum: O(2^(N/2) * N) time and O(2^(N/2)) space, about 2 * 10^7 steps at N = 40 instead of 2^40 sums.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| List every choice of one half, the empty one included | sums = [0]
sums += [s + x for s in sums] | Each new number doubles the list: every old sum stays (the number is skipped) and comes back with the number added. Starting from `[0]` keeps the choice that takes nothing from this half. |
| Split into two halves | left = all_sums(nums[:half])
right = sorted(all_sums(nums[half:])) | Each half has at most 20 numbers, so each list has at most 2^20 sums. Every subsequence of `nums` is one left choice plus one right choice. |
| Sort one side so it can be searched | right = sorted(all_sums(nums[half:])) | Only `right` is searched, so only `right` needs sorting; `left` is read in any order. |
| For each left sum, what the right half should add | need = goal - s
k = bisect_left(right, need) | `s + r` is closest to `goal` exactly when `r` is closest to `need`, and in a sorted list that value sits next to the insertion point `k`. |
| Both neighbours of the insertion point (the trap) | best = min(best, right[k] - need)
best = min(best, need - right[k - 1]) | `right[k]` is the closest sum from above and `right[k - 1]` the closest from below; either can win, so both are checked, each only when it exists. |
| The answer | return best | `best` has seen the closest right sum for every left sum, so it is the smallest distance of any subsequence. |