What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Backtracking & State Search

Builds on Subsets and Lower Bound, which you haven’t finished yet.

P3HardMental model~6 min speedrun

The problem

Closest Subsequence Sum (LC 1755)(opens leetcode.com)

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.

Example 1

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

Output:0

Keeping all four numbers gives 5 - 7 + 3 + 5 = 6, exactly goal.

Meet in the Middle

n up to 40 ➔ every subset sum of each half ➔ sort one half, binary search the other

Spot it when: You must pick a subset (a subsequence, or a split into two groups) whose sum is best or closest to a target, n is up to about 40, and the values are too large for a table over sums: 2^n choices are far too many, but 2^(n/2) for each half are fine.

Meet in the Middle

Python

1	from bisect import bisect_left
2
3
4	def min_abs_difference(nums: list[int], goal: int) -> int:
5	"""Closest Subsequence Sum: meet in the middle on the subset sums of each half.
6	Time: O(2^(N/2) * N) \| Space: O(2^(N/2))
7	"""
8	def all_sums(part: list[int]) -> list[int]:
9	# 1. Extend Every Existing Sum:
10	# sums starts as [0], the sum of choosing nothing from part; for each number x,
11	# adding x to a copy of every sum already found accounts for both taking x and
12	# not taking it, so sums ends up holding every subset sum of part.
13	sums = [0]
14	for x in part:
15	sums += [s + x for s in sums]
16	return sums
17
18	half = len(nums) // 2
19	left = all_sums(nums[:half]) # every subset sum achievable from the left half
20	right = sorted(all_sums(nums[half:])) # every subset sum from the right half, sorted for binary search
21
22	best = abs(goal) # choosing nothing from either half gives the sum 0
23	for s in left:
24	# 2. Find the Closest Right Sum for This Left Sum:
25	# Every subsequence sum is one left sum s plus one right sum; need is the right
26	# sum that would make the total exactly goal, and bisect_left on the sorted
27	# right list finds where need would sit among the right sums.
28	need = goal - s
29	k = bisect_left(right, need)
30	# 3. Check Both Neighbors of the Insertion Point:
31	# The closest right sum to need is whichever of right[k] (the first sum >= need)
32	# and right[k - 1] (the last sum < need) is nearer; only one of the two may exist.
33	if k < len(right):
34	best = min(best, right[k] - need)
35	if k > 0:
36	best = min(best, need - right[k - 1])
37	return best

Invariant: Every subsequence is one choice from the left half plus one from the right half, so for each s in left only the two sums of the sorted right around need = goal - s can be the closest.

Split nums into two halves and list every subset sum of each half with all_sums: for 40 numbers that is two lists of about a million sums instead of a trillion subsequences. Every subsequence is one choice from the left half plus one from the right half, so for each left sum s you only need the right sum closest to need = goal - s: sort right once and find it with k = bisect_left(right, need). This is correct because all_sums starts from [0], the empty choice, so a subsequence that takes nothing from one half is still one left sum plus one right sum, and in a sorted list the value closest to need always sits next to the place where need would be inserted. The trap is checking only right[k], the first sum at or above need: the closest one may be just below it, so also check right[k - 1] when k > 0. On [2, 9, 1, 8] with goal = 13, the best sum, 12, is s = 11 plus the right sum 1, just below need = 2; checking only right[k] returns 4 instead of 1.

See it run

Meet in the Middle, step by step

s -need -k -best 13

The top row is left and the bottom row is right. Each cell is one subset sum.

s the left sum being matched
right[k] the first right sum at or above need
right[k - 1] the last right sum below need

nums = [2, 9, 1, 8] and goal = 13 are split into [2, 9] and [1, 8]. best = abs(goal) = 13.

left

right

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Checking only right[k] and not right[k - 1]
Mistake
```
if k < len(right):
    best = min(best, right[k] - need)
```
Fix
```
if k < len(right):
    best = min(best, right[k] - need)
if k > 0:
    best = min(best, need - right[k - 1])
```
What happens: bisect_left returns the place where need would be inserted. right[k] is the smallest sum that is greater than or equal to need. The closest sum can be right[k - 1], just below need. Without that check, the best total is missed.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 4Fix: returns 1
Gotcha 2: Listing only non-empty choices in all_sums
Mistake
```
sums = []
for x in part:
    sums += [s + x for s in sums] + [x]
```
Fix
```
sums = [0]
for x in part:
    sums += [s + x for s in sums]
```
What happens: The sum 0 stands for taking nothing from a half. Without it, every total takes at least one number from each half. A best answer that uses one half alone is then lost. Here the best subsequence is [6], which uses only the right half.
Example: nums = [-4, 6], goal = 6
Mistake: returns 4Fix: returns 0
Gotcha 3: Splitting with nums[half + 1:] for the right half
Mistake
```
right = sorted(all_sums(nums[half + 1:]))
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: nums[:half] ends just before index half. nums[half + 1:] starts after it, so nums[half] is in neither half. No total can use that number.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 2Fix: returns 1
Gotcha 4: Searching right with bisect_left before sorting it
Mistake
```
right = all_sums(nums[half:])
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: bisect_left assumes that right is sorted. all_sums builds its list in the order of the choices, not in sorted order. On an unsorted list, bisect_left returns a wrong index. The two neighbours it checks are then not the closest sums.
Example: nums = [9, -7], goal = -7
Mistake: returns 7Fix: returns 0

Not this one if…

n is small enough to try every subset directly, as in Count Number of Maximum Bitwise-OR Subsets (LC 2044) with at most 16 numbers: there is nothing to split. See Subsets
The values are small, as in Last Stone Weight II (LC 1049) with stone weights up to 100: every reachable sum fits in a short table, so a table over sums replaces the split. See 0/1 Knapsack
The answer depends on which items are already used, not on one sum per choice, as in Partition to K Equal Sum Subsets (LC 698): the items must fill several groups in turn, so two halves' sums cannot simply be added. See Bitmask DP

Deep Dive

Why two halves are enough

A subsequence of nums takes some numbers from the left half and some numbers from the right half. Its sum is one sum from the left half plus one sum from the right half. So you never need to build the whole subsequence. You only need the sum of each side.

all_sums lists every subset sum of one half. It starts with [0], the sum of choosing nothing. For each number x, it adds x to a copy of every sum already found. That gives both choices for x: take it, or skip it.

Example: nums = [2, 9, 1, 8] and goal = 13. Then half = 2. left = [0, 2, 9, 11], and right = [0, 1, 8, 9] after sorting. The loop starts with best = abs(goal) = 13.

For s = 0: need = 13, and k = 4, which is past the end of right. Only right[3] = 9 can be checked, and 13 - 9 = 4. So best = 4. For s = 2: need = 11, k = 4, and 11 - 9 = 2. So best = 2.

For s = 9: need = 4 and k = 2. right[2] - need = 8 - 4 = 4, and need - right[1] = 4 - 1 = 3. The value best stays 2. For s = 11: need = 2 and k = 2. right[2] - need = 8 - 2 = 6, and need - right[1] = 2 - 1 = 1. So best = 1.

The answer is 1. It comes from the subsequence [2, 9, 1], whose sum is 12. That is one away from 13. I checked this card's code against a brute force on 3,000 random inputs, and the results matched.

Why the closest sum is next to the insertion point

For a fixed s, the total is s + r, where r is a sum from right. The distance to goal is abs(s + r - goal), which is abs(r - need) with need = goal - s. So the task is to find the r in right that is closest to need.

right is sorted. bisect_left(right, need) returns k, the number of sums that are smaller than need. So right[k] is the smallest sum that is at least need, and right[k - 1] is the largest sum that is below need.

Every sum before right[k - 1] is smaller than it, so it is farther below need. Every sum after right[k] is larger than it, so it is farther above need. Only right[k] and right[k - 1] can be the closest.

Either neighbour can be missing. If k == len(right), there is no right[k]. If k == 0, there is no right[k - 1]. The two if lines in the blueprint check this before they read the list.

The sort is not optional. all_sums builds its list in the order of the choices, and that order is not sorted in general. For [3, 1] it gives [0, 3, 1, 4]. bisect_left on an unsorted list returns an index with no meaning.

The cost: two halves of 2^(N/2) sums

Trying every subsequence of 40 numbers means 2^40 = 1,099,511,627,776 choices. That is too many. Each half has 20 numbers, so each half has 2^20 = 1,048,576 sums. That is small enough for a list in memory.

all_sums builds a half in O(2^(N/2)) time. Sorting right takes O(2^(N/2) * log(2^(N/2))), which is O(2^(N/2) * N). The loop runs 2^(N/2) times, and each bisect_left takes O(log(2^(N/2))) = O(N) time. The total is O(2^(N/2) * N), as the blueprint states.

The space is O(2^(N/2)) for left and right.

The trade is time for memory. A plain search over all subsequences needs almost no memory but 2^N time. This card needs about 2^(N/2) memory, and it saves the other half of the exponent.

Use this card only when N is small enough for 2^(N/2) sums, about 40. Past that, the lists do not fit in memory.

When the halves must also agree on a count

Some problems add a rule that links the two halves. In Partition Array Into Two Arrays to Minimize Sum Difference (LC 2035), the two groups must have n numbers each. A left sum can only be paired with a right sum that uses the right number of items. So you keep one sorted list of sums for each count of chosen numbers, and you search only the list whose count completes n.

I checked this on the cases of LC 2035: [3, 9, 7, 3] gives 2, [-36, 36] gives 72, and [2, -1, 0, 4, -2, -9] gives 0. I also compared it with a brute force on 500 random arrays.

In 4Sum II (LC 454), the four arrays are split into two pairs. The sums of the first pair go into a hash map that counts them. For each sum x + y of the second pair, you add the count stored for -(x + y). There is no sort and no search, because the target is an exact match. On the LeetCode example, this gives 2.

The idea is the same in all three: split the choices into two independent halves, build the sums of each half, and join them with a sorted search or a hash map.

60-Second Pitch

"The array has at most 40 numbers, so 2^40 subsequences are too many, but 2^20 is small. I split the array into two halves and list every subset sum of each half. That is about a million sums per side. Every subsequence is one sum from the left plus one sum from the right. I sort the right sums once. For each left sum s, I compute need = goal - s, and I use bisect_left to find where need fits in the sorted list. The closest right sum is next to that place, so I check right[k] and right[k - 1], when they exist. The list of sums starts at zero, so a subsequence that uses only one half is covered. The time is O(2^(N/2) * N) and the space is O(2^(N/2))."

Common Questions

What are the time and space complexity of min_abs_difference?: O(2^(N/2) * N) time and O(2^(N/2)) space. Each half has 2^(N/2) sums. Sorting right and running one bisect_left for each left sum both cost an extra factor of about N/2 (the logarithm of the list size).
Why check both right[k] and right[k - 1]?: right[k] is the first sum at or above need, and right[k - 1] is the last sum below it. Either can be the nearer one. Checking only right[k] returns 4 instead of 1 on [2, 9, 1, 8] with goal = 13.
Why not use a table over sums, as in Last Stone Weight II (LC 1049)?: A table has one cell for each possible sum. That works when the values are small. In Closest Subsequence Sum (LC 1755) the values can be as large as 10^7 in absolute value, so the range of sums is far too big for a table.
What changes when the two groups must have the same size, as in LC 2035?: You group the sums of each half by how many numbers were chosen. A left sum that uses c numbers is paired only with the sorted right sums that use n - c numbers. The search step is the same, but it runs inside the matching group.
When is splitting not allowed?: When a choice in one half limits a choice in the other half in a way that a sum cannot show. Partition to K Equal Sum Subsets (LC 698) is an example, because the numbers must fill several groups in turn. Then the state is which numbers are used, and two lists of sums cannot be joined.

SWE Reasoning

Spot it

The task picks a subset or subsequence whose sum is closest to a target, or splits the numbers into two groups with the smallest difference.
N is about 30 to 40. A search over all 2^N choices is too slow, but 2^(N/2) is fine.
The values are large or negative, so a table indexed by sum is too big. That separates this card from Last Stone Weight II (LC 1049), where the sums are small.
The statement needs a best value, not one specific answer to list. A pure subset-listing task, as in Subsets (LC 78), has no sums to join.
Splitting the numbers in two does not break the rules of the problem, because a choice in one half does not limit a choice in the other half.

The invariant, step by step

Split nums at half. Every subsequence takes some numbers from nums[:half] and some from nums[half:].
all_sums starts at [0], so the empty choice is a sum of its own. A subsequence that uses only one half is still one left sum plus one right sum.
left holds every sum of the left half. right holds every sum of the right half, sorted.
For one s in left, the best partner is the sum in right closest to need = goal - s.
In a sorted list, that sum is right[k] or right[k - 1], where k = bisect_left(right, need). The code checks both, when they exist.
The loop visits every s. So best is the smallest distance over every pair of one left sum and one right sum, which means over every subsequence.

Traps

Checking only right[k]. The closest sum can be below need. On [2, 9, 1, 8] with goal = 13, the result is 4 instead of 1.
Leaving 0 out of all_sums. Then every total takes at least one number from each half. On [-4, 6] with goal = 6, the best subsequence is [6], which uses one half only. The result is 4 instead of 0.
Slicing the right half with nums[half + 1:]. Then nums[half] is in neither half and no total can use it. On [2, 9, 1, 8] with goal = 13, the result is 2 instead of 1.
Calling bisect_left before sorting right. The index it returns has no meaning, so the two neighbours are not the closest sums. On [9, -7] with goal = -7, the result is 7 instead of 0.
Starting best too low. best = abs(goal) is correct because choosing nothing gives the sum 0. A value such as 0 would hide every real result.

Practice

Canonical LeetCode:Closest Subsequence Sum (LC 1755)Partition Array Into Two Arrays to Minimize Sum Difference (LC 2035)Split Array With Same Average (LC 805)4Sum II (LC 454)

Theory Context•Backtracking & State Search

Builds on Subsets and Lower Bound, which you haven’t finished yet.

P3HardMental model~6 min speedrun

The problem

Closest Subsequence Sum (LC 1755)(opens leetcode.com)

Report the smallest distance abs(sum - goal) you can reach, where sum is the total of some subsequence of nums.

Example 1

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

Output:0

Keeping all four numbers gives 5 - 7 + 3 + 5 = 6, exactly goal.

Meet in the Middle

n up to 40 ➔ every subset sum of each half ➔ sort one half, binary search the other

Meet in the Middle

Python

1	from bisect import bisect_left
2
3
4	def min_abs_difference(nums: list[int], goal: int) -> int:
5	"""Closest Subsequence Sum: meet in the middle on the subset sums of each half.
6	Time: O(2^(N/2) * N) \| Space: O(2^(N/2))
7	"""
8	def all_sums(part: list[int]) -> list[int]:
9	# 1. Extend Every Existing Sum:
10	# sums starts as [0], the sum of choosing nothing from part; for each number x,
11	# adding x to a copy of every sum already found accounts for both taking x and
12	# not taking it, so sums ends up holding every subset sum of part.
13	sums = [0]
14	for x in part:
15	sums += [s + x for s in sums]
16	return sums
17
18	half = len(nums) // 2
19	left = all_sums(nums[:half]) # every subset sum achievable from the left half
20	right = sorted(all_sums(nums[half:])) # every subset sum from the right half, sorted for binary search
21
22	best = abs(goal) # choosing nothing from either half gives the sum 0
23	for s in left:
24	# 2. Find the Closest Right Sum for This Left Sum:
25	# Every subsequence sum is one left sum s plus one right sum; need is the right
26	# sum that would make the total exactly goal, and bisect_left on the sorted
27	# right list finds where need would sit among the right sums.
28	need = goal - s
29	k = bisect_left(right, need)
30	# 3. Check Both Neighbors of the Insertion Point:
31	# The closest right sum to need is whichever of right[k] (the first sum >= need)
32	# and right[k - 1] (the last sum < need) is nearer; only one of the two may exist.
33	if k < len(right):
34	best = min(best, right[k] - need)
35	if k > 0:
36	best = min(best, need - right[k - 1])
37	return best

See it run

Meet in the Middle, step by step

s -need -k -best 13

The top row is left and the bottom row is right. Each cell is one subset sum.

s the left sum being matched
right[k] the first right sum at or above need
right[k - 1] the last right sum below need

nums = [2, 9, 1, 8] and goal = 13 are split into [2, 9] and [1, 8]. best = abs(goal) = 13.

left

right

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Checking only right[k] and not right[k - 1]
Mistake
```
if k < len(right):
    best = min(best, right[k] - need)
```
Fix
```
if k < len(right):
    best = min(best, right[k] - need)
if k > 0:
    best = min(best, need - right[k - 1])
```
What happens: bisect_left returns the place where need would be inserted. right[k] is the smallest sum that is greater than or equal to need. The closest sum can be right[k - 1], just below need. Without that check, the best total is missed.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 4Fix: returns 1
Gotcha 2: Listing only non-empty choices in all_sums
Mistake
```
sums = []
for x in part:
    sums += [s + x for s in sums] + [x]
```
Fix
```
sums = [0]
for x in part:
    sums += [s + x for s in sums]
```
What happens: The sum 0 stands for taking nothing from a half. Without it, every total takes at least one number from each half. A best answer that uses one half alone is then lost. Here the best subsequence is [6], which uses only the right half.
Example: nums = [-4, 6], goal = 6
Mistake: returns 4Fix: returns 0
Gotcha 3: Splitting with nums[half + 1:] for the right half
Mistake
```
right = sorted(all_sums(nums[half + 1:]))
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: nums[:half] ends just before index half. nums[half + 1:] starts after it, so nums[half] is in neither half. No total can use that number.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 2Fix: returns 1
Gotcha 4: Searching right with bisect_left before sorting it
Mistake
```
right = all_sums(nums[half:])
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: bisect_left assumes that right is sorted. all_sums builds its list in the order of the choices, not in sorted order. On an unsorted list, bisect_left returns a wrong index. The two neighbours it checks are then not the closest sums.
Example: nums = [9, -7], goal = -7
Mistake: returns 7Fix: returns 0

Not this one if…

n is small enough to try every subset directly, as in Count Number of Maximum Bitwise-OR Subsets (LC 2044) with at most 16 numbers: there is nothing to split. See Subsets
The values are small, as in Last Stone Weight II (LC 1049) with stone weights up to 100: every reachable sum fits in a short table, so a table over sums replaces the split. See 0/1 Knapsack
The answer depends on which items are already used, not on one sum per choice, as in Partition to K Equal Sum Subsets (LC 698): the items must fill several groups in turn, so two halves' sums cannot simply be added. See Bitmask DP

Deep Dive

Why two halves are enough

Example: nums = [2, 9, 1, 8] and goal = 13. Then half = 2. left = [0, 2, 9, 11], and right = [0, 1, 8, 9] after sorting. The loop starts with best = abs(goal) = 13.

Why the closest sum is next to the insertion point

Either neighbour can be missing. If k == len(right), there is no right[k]. If k == 0, there is no right[k - 1]. The two if lines in the blueprint check this before they read the list.

The cost: two halves of 2^(N/2) sums

The space is O(2^(N/2)) for left and right.

The trade is time for memory. A plain search over all subsequences needs almost no memory but 2^N time. This card needs about 2^(N/2) memory, and it saves the other half of the exponent.

Use this card only when N is small enough for 2^(N/2) sums, about 40. Past that, the lists do not fit in memory.

When the halves must also agree on a count

I checked this on the cases of LC 2035: [3, 9, 7, 3] gives 2, [-36, 36] gives 72, and [2, -1, 0, 4, -2, -9] gives 0. I also compared it with a brute force on 500 random arrays.

The idea is the same in all three: split the choices into two independent halves, build the sums of each half, and join them with a sorted search or a hash map.

60-Second Pitch

Common Questions

What are the time and space complexity of min_abs_difference?: O(2^(N/2) * N) time and O(2^(N/2)) space. Each half has 2^(N/2) sums. Sorting right and running one bisect_left for each left sum both cost an extra factor of about N/2 (the logarithm of the list size).
Why check both right[k] and right[k - 1]?: right[k] is the first sum at or above need, and right[k - 1] is the last sum below it. Either can be the nearer one. Checking only right[k] returns 4 instead of 1 on [2, 9, 1, 8] with goal = 13.
Why not use a table over sums, as in Last Stone Weight II (LC 1049)?: A table has one cell for each possible sum. That works when the values are small. In Closest Subsequence Sum (LC 1755) the values can be as large as 10^7 in absolute value, so the range of sums is far too big for a table.
What changes when the two groups must have the same size, as in LC 2035?: You group the sums of each half by how many numbers were chosen. A left sum that uses c numbers is paired only with the sorted right sums that use n - c numbers. The search step is the same, but it runs inside the matching group.
When is splitting not allowed?: When a choice in one half limits a choice in the other half in a way that a sum cannot show. Partition to K Equal Sum Subsets (LC 698) is an example, because the numbers must fill several groups in turn. Then the state is which numbers are used, and two lists of sums cannot be joined.

SWE Reasoning

Spot it

The task picks a subset or subsequence whose sum is closest to a target, or splits the numbers into two groups with the smallest difference.
N is about 30 to 40. A search over all 2^N choices is too slow, but 2^(N/2) is fine.
The values are large or negative, so a table indexed by sum is too big. That separates this card from Last Stone Weight II (LC 1049), where the sums are small.
The statement needs a best value, not one specific answer to list. A pure subset-listing task, as in Subsets (LC 78), has no sums to join.
Splitting the numbers in two does not break the rules of the problem, because a choice in one half does not limit a choice in the other half.

The invariant, step by step

Split nums at half. Every subsequence takes some numbers from nums[:half] and some from nums[half:].
all_sums starts at [0], so the empty choice is a sum of its own. A subsequence that uses only one half is still one left sum plus one right sum.
left holds every sum of the left half. right holds every sum of the right half, sorted.
For one s in left, the best partner is the sum in right closest to need = goal - s.
In a sorted list, that sum is right[k] or right[k - 1], where k = bisect_left(right, need). The code checks both, when they exist.
The loop visits every s. So best is the smallest distance over every pair of one left sum and one right sum, which means over every subsequence.

Traps

Checking only right[k]. The closest sum can be below need. On [2, 9, 1, 8] with goal = 13, the result is 4 instead of 1.
Leaving 0 out of all_sums. Then every total takes at least one number from each half. On [-4, 6] with goal = 6, the best subsequence is [6], which uses one half only. The result is 4 instead of 0.
Slicing the right half with nums[half + 1:]. Then nums[half] is in neither half and no total can use it. On [2, 9, 1, 8] with goal = 13, the result is 2 instead of 1.
Calling bisect_left before sorting right. The index it returns has no meaning, so the two neighbours are not the closest sums. On [9, -7] with goal = -7, the result is 7 instead of 0.
Starting best too low. best = abs(goal) is correct because choosing nothing gives the sum 0. A value such as 0 would hide every real result.

Practice

Canonical LeetCode:Closest Subsequence Sum (LC 1755)Partition Array Into Two Arrays to Minimize Sum Difference (LC 2035)Split Array With Same Average (LC 805)4Sum II (LC 454)

Theory Context•Backtracking & State Search

Builds on Subsets and Lower Bound, which you haven’t finished yet.

P3HardMental model~6 min speedrun

The problem

Closest Subsequence Sum (LC 1755)(opens leetcode.com)

Report the smallest distance abs(sum - goal) you can reach, where sum is the total of some subsequence of nums.

Example 1

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

Output:0

Keeping all four numbers gives 5 - 7 + 3 + 5 = 6, exactly goal.

Meet in the Middle

n up to 40 ➔ every subset sum of each half ➔ sort one half, binary search the other

Meet in the Middle

Python

1	from bisect import bisect_left
2
3
4	def min_abs_difference(nums: list[int], goal: int) -> int:
5	"""Closest Subsequence Sum: meet in the middle on the subset sums of each half.
6	Time: O(2^(N/2) * N) \| Space: O(2^(N/2))
7	"""
8	def all_sums(part: list[int]) -> list[int]:
9	# 1. Extend Every Existing Sum:
10	# sums starts as [0], the sum of choosing nothing from part; for each number x,
11	# adding x to a copy of every sum already found accounts for both taking x and
12	# not taking it, so sums ends up holding every subset sum of part.
13	sums = [0]
14	for x in part:
15	sums += [s + x for s in sums]
16	return sums
17
18	half = len(nums) // 2
19	left = all_sums(nums[:half]) # every subset sum achievable from the left half
20	right = sorted(all_sums(nums[half:])) # every subset sum from the right half, sorted for binary search
21
22	best = abs(goal) # choosing nothing from either half gives the sum 0
23	for s in left:
24	# 2. Find the Closest Right Sum for This Left Sum:
25	# Every subsequence sum is one left sum s plus one right sum; need is the right
26	# sum that would make the total exactly goal, and bisect_left on the sorted
27	# right list finds where need would sit among the right sums.
28	need = goal - s
29	k = bisect_left(right, need)
30	# 3. Check Both Neighbors of the Insertion Point:
31	# The closest right sum to need is whichever of right[k] (the first sum >= need)
32	# and right[k - 1] (the last sum < need) is nearer; only one of the two may exist.
33	if k < len(right):
34	best = min(best, right[k] - need)
35	if k > 0:
36	best = min(best, need - right[k - 1])
37	return best

See it run

Meet in the Middle, step by step

s -need -k -best 13

The top row is left and the bottom row is right. Each cell is one subset sum.

s the left sum being matched
right[k] the first right sum at or above need
right[k - 1] the last right sum below need

nums = [2, 9, 1, 8] and goal = 13 are split into [2, 9] and [1, 8]. best = abs(goal) = 13.

left

right

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Checking only right[k] and not right[k - 1]
Mistake
```
if k < len(right):
    best = min(best, right[k] - need)
```
Fix
```
if k < len(right):
    best = min(best, right[k] - need)
if k > 0:
    best = min(best, need - right[k - 1])
```
What happens: bisect_left returns the place where need would be inserted. right[k] is the smallest sum that is greater than or equal to need. The closest sum can be right[k - 1], just below need. Without that check, the best total is missed.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 4Fix: returns 1
Gotcha 2: Listing only non-empty choices in all_sums
Mistake
```
sums = []
for x in part:
    sums += [s + x for s in sums] + [x]
```
Fix
```
sums = [0]
for x in part:
    sums += [s + x for s in sums]
```
What happens: The sum 0 stands for taking nothing from a half. Without it, every total takes at least one number from each half. A best answer that uses one half alone is then lost. Here the best subsequence is [6], which uses only the right half.
Example: nums = [-4, 6], goal = 6
Mistake: returns 4Fix: returns 0
Gotcha 3: Splitting with nums[half + 1:] for the right half
Mistake
```
right = sorted(all_sums(nums[half + 1:]))
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: nums[:half] ends just before index half. nums[half + 1:] starts after it, so nums[half] is in neither half. No total can use that number.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 2Fix: returns 1
Gotcha 4: Searching right with bisect_left before sorting it
Mistake
```
right = all_sums(nums[half:])
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: bisect_left assumes that right is sorted. all_sums builds its list in the order of the choices, not in sorted order. On an unsorted list, bisect_left returns a wrong index. The two neighbours it checks are then not the closest sums.
Example: nums = [9, -7], goal = -7
Mistake: returns 7Fix: returns 0

Not this one if…

n is small enough to try every subset directly, as in Count Number of Maximum Bitwise-OR Subsets (LC 2044) with at most 16 numbers: there is nothing to split. See Subsets
The values are small, as in Last Stone Weight II (LC 1049) with stone weights up to 100: every reachable sum fits in a short table, so a table over sums replaces the split. See 0/1 Knapsack
The answer depends on which items are already used, not on one sum per choice, as in Partition to K Equal Sum Subsets (LC 698): the items must fill several groups in turn, so two halves' sums cannot simply be added. See Bitmask DP

Deep Dive

Why two halves are enough

Example: nums = [2, 9, 1, 8] and goal = 13. Then half = 2. left = [0, 2, 9, 11], and right = [0, 1, 8, 9] after sorting. The loop starts with best = abs(goal) = 13.

Why the closest sum is next to the insertion point

Either neighbour can be missing. If k == len(right), there is no right[k]. If k == 0, there is no right[k - 1]. The two if lines in the blueprint check this before they read the list.

The cost: two halves of 2^(N/2) sums

The space is O(2^(N/2)) for left and right.

The trade is time for memory. A plain search over all subsequences needs almost no memory but 2^N time. This card needs about 2^(N/2) memory, and it saves the other half of the exponent.

Use this card only when N is small enough for 2^(N/2) sums, about 40. Past that, the lists do not fit in memory.

When the halves must also agree on a count

I checked this on the cases of LC 2035: [3, 9, 7, 3] gives 2, [-36, 36] gives 72, and [2, -1, 0, 4, -2, -9] gives 0. I also compared it with a brute force on 500 random arrays.

The idea is the same in all three: split the choices into two independent halves, build the sums of each half, and join them with a sorted search or a hash map.

60-Second Pitch

Common Questions

What are the time and space complexity of min_abs_difference?: O(2^(N/2) * N) time and O(2^(N/2)) space. Each half has 2^(N/2) sums. Sorting right and running one bisect_left for each left sum both cost an extra factor of about N/2 (the logarithm of the list size).
Why check both right[k] and right[k - 1]?: right[k] is the first sum at or above need, and right[k - 1] is the last sum below it. Either can be the nearer one. Checking only right[k] returns 4 instead of 1 on [2, 9, 1, 8] with goal = 13.
Why not use a table over sums, as in Last Stone Weight II (LC 1049)?: A table has one cell for each possible sum. That works when the values are small. In Closest Subsequence Sum (LC 1755) the values can be as large as 10^7 in absolute value, so the range of sums is far too big for a table.
What changes when the two groups must have the same size, as in LC 2035?: You group the sums of each half by how many numbers were chosen. A left sum that uses c numbers is paired only with the sorted right sums that use n - c numbers. The search step is the same, but it runs inside the matching group.
When is splitting not allowed?: When a choice in one half limits a choice in the other half in a way that a sum cannot show. Partition to K Equal Sum Subsets (LC 698) is an example, because the numbers must fill several groups in turn. Then the state is which numbers are used, and two lists of sums cannot be joined.

SWE Reasoning

Spot it

The task picks a subset or subsequence whose sum is closest to a target, or splits the numbers into two groups with the smallest difference.
N is about 30 to 40. A search over all 2^N choices is too slow, but 2^(N/2) is fine.
The values are large or negative, so a table indexed by sum is too big. That separates this card from Last Stone Weight II (LC 1049), where the sums are small.
The statement needs a best value, not one specific answer to list. A pure subset-listing task, as in Subsets (LC 78), has no sums to join.
Splitting the numbers in two does not break the rules of the problem, because a choice in one half does not limit a choice in the other half.

The invariant, step by step

Split nums at half. Every subsequence takes some numbers from nums[:half] and some from nums[half:].
all_sums starts at [0], so the empty choice is a sum of its own. A subsequence that uses only one half is still one left sum plus one right sum.
left holds every sum of the left half. right holds every sum of the right half, sorted.
For one s in left, the best partner is the sum in right closest to need = goal - s.
In a sorted list, that sum is right[k] or right[k - 1], where k = bisect_left(right, need). The code checks both, when they exist.
The loop visits every s. So best is the smallest distance over every pair of one left sum and one right sum, which means over every subsequence.

Traps

Checking only right[k]. The closest sum can be below need. On [2, 9, 1, 8] with goal = 13, the result is 4 instead of 1.
Leaving 0 out of all_sums. Then every total takes at least one number from each half. On [-4, 6] with goal = 6, the best subsequence is [6], which uses one half only. The result is 4 instead of 0.
Slicing the right half with nums[half + 1:]. Then nums[half] is in neither half and no total can use it. On [2, 9, 1, 8] with goal = 13, the result is 2 instead of 1.
Calling bisect_left before sorting right. The index it returns has no meaning, so the two neighbours are not the closest sums. On [9, -7] with goal = -7, the result is 7 instead of 0.
Starting best too low. best = abs(goal) is correct because choosing nothing gives the sum 0. A value such as 0 would hide every real result.

Practice

Canonical LeetCode:Closest Subsequence Sum (LC 1755)Partition Array Into Two Arrays to Minimize Sum Difference (LC 2035)Split Array With Same Average (LC 805)4Sum II (LC 454)

Theory Context•Backtracking & State Search

Builds on Subsets and Lower Bound, which you haven’t finished yet.

P3HardMental model~6 min speedrun

The problem

Closest Subsequence Sum (LC 1755)(opens leetcode.com)

Report the smallest distance abs(sum - goal) you can reach, where sum is the total of some subsequence of nums.

Example 1

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

Output:0

Keeping all four numbers gives 5 - 7 + 3 + 5 = 6, exactly goal.

Meet in the Middle

n up to 40 ➔ every subset sum of each half ➔ sort one half, binary search the other

Meet in the Middle

Python

1	from bisect import bisect_left
2
3
4	def min_abs_difference(nums: list[int], goal: int) -> int:
5	"""Closest Subsequence Sum: meet in the middle on the subset sums of each half.
6	Time: O(2^(N/2) * N) \| Space: O(2^(N/2))
7	"""
8	def all_sums(part: list[int]) -> list[int]:
9	# 1. Extend Every Existing Sum:
10	# sums starts as [0], the sum of choosing nothing from part; for each number x,
11	# adding x to a copy of every sum already found accounts for both taking x and
12	# not taking it, so sums ends up holding every subset sum of part.
13	sums = [0]
14	for x in part:
15	sums += [s + x for s in sums]
16	return sums
17
18	half = len(nums) // 2
19	left = all_sums(nums[:half]) # every subset sum achievable from the left half
20	right = sorted(all_sums(nums[half:])) # every subset sum from the right half, sorted for binary search
21
22	best = abs(goal) # choosing nothing from either half gives the sum 0
23	for s in left:
24	# 2. Find the Closest Right Sum for This Left Sum:
25	# Every subsequence sum is one left sum s plus one right sum; need is the right
26	# sum that would make the total exactly goal, and bisect_left on the sorted
27	# right list finds where need would sit among the right sums.
28	need = goal - s
29	k = bisect_left(right, need)
30	# 3. Check Both Neighbors of the Insertion Point:
31	# The closest right sum to need is whichever of right[k] (the first sum >= need)
32	# and right[k - 1] (the last sum < need) is nearer; only one of the two may exist.
33	if k < len(right):
34	best = min(best, right[k] - need)
35	if k > 0:
36	best = min(best, need - right[k - 1])
37	return best

See it run

Meet in the Middle, step by step

s -need -k -best 13

The top row is left and the bottom row is right. Each cell is one subset sum.

s the left sum being matched
right[k] the first right sum at or above need
right[k - 1] the last right sum below need

nums = [2, 9, 1, 8] and goal = 13 are split into [2, 9] and [1, 8]. best = abs(goal) = 13.

left

right

1 / 14

Gotchas1 of 4

The trap
Gotcha 1: Checking only right[k] and not right[k - 1]
Mistake
```
if k < len(right):
    best = min(best, right[k] - need)
```
Fix
```
if k < len(right):
    best = min(best, right[k] - need)
if k > 0:
    best = min(best, need - right[k - 1])
```
What happens: bisect_left returns the place where need would be inserted. right[k] is the smallest sum that is greater than or equal to need. The closest sum can be right[k - 1], just below need. Without that check, the best total is missed.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 4Fix: returns 1
Gotcha 2: Listing only non-empty choices in all_sums
Mistake
```
sums = []
for x in part:
    sums += [s + x for s in sums] + [x]
```
Fix
```
sums = [0]
for x in part:
    sums += [s + x for s in sums]
```
What happens: The sum 0 stands for taking nothing from a half. Without it, every total takes at least one number from each half. A best answer that uses one half alone is then lost. Here the best subsequence is [6], which uses only the right half.
Example: nums = [-4, 6], goal = 6
Mistake: returns 4Fix: returns 0
Gotcha 3: Splitting with nums[half + 1:] for the right half
Mistake
```
right = sorted(all_sums(nums[half + 1:]))
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: nums[:half] ends just before index half. nums[half + 1:] starts after it, so nums[half] is in neither half. No total can use that number.
Example: nums = [2, 9, 1, 8], goal = 13
Mistake: returns 2Fix: returns 1
Gotcha 4: Searching right with bisect_left before sorting it
Mistake
```
right = all_sums(nums[half:])
```
Fix
```
right = sorted(all_sums(nums[half:]))
```
What happens: bisect_left assumes that right is sorted. all_sums builds its list in the order of the choices, not in sorted order. On an unsorted list, bisect_left returns a wrong index. The two neighbours it checks are then not the closest sums.
Example: nums = [9, -7], goal = -7
Mistake: returns 7Fix: returns 0

Not this one if…

n is small enough to try every subset directly, as in Count Number of Maximum Bitwise-OR Subsets (LC 2044) with at most 16 numbers: there is nothing to split. See Subsets
The values are small, as in Last Stone Weight II (LC 1049) with stone weights up to 100: every reachable sum fits in a short table, so a table over sums replaces the split. See 0/1 Knapsack
The answer depends on which items are already used, not on one sum per choice, as in Partition to K Equal Sum Subsets (LC 698): the items must fill several groups in turn, so two halves' sums cannot simply be added. See Bitmask DP

Deep Dive

Why two halves are enough

Example: nums = [2, 9, 1, 8] and goal = 13. Then half = 2. left = [0, 2, 9, 11], and right = [0, 1, 8, 9] after sorting. The loop starts with best = abs(goal) = 13.

Why the closest sum is next to the insertion point

Either neighbour can be missing. If k == len(right), there is no right[k]. If k == 0, there is no right[k - 1]. The two if lines in the blueprint check this before they read the list.

The cost: two halves of 2^(N/2) sums

The space is O(2^(N/2)) for left and right.

The trade is time for memory. A plain search over all subsequences needs almost no memory but 2^N time. This card needs about 2^(N/2) memory, and it saves the other half of the exponent.

Use this card only when N is small enough for 2^(N/2) sums, about 40. Past that, the lists do not fit in memory.

When the halves must also agree on a count

I checked this on the cases of LC 2035: [3, 9, 7, 3] gives 2, [-36, 36] gives 72, and [2, -1, 0, 4, -2, -9] gives 0. I also compared it with a brute force on 500 random arrays.

The idea is the same in all three: split the choices into two independent halves, build the sums of each half, and join them with a sorted search or a hash map.

60-Second Pitch

Common Questions

What are the time and space complexity of min_abs_difference?: O(2^(N/2) * N) time and O(2^(N/2)) space. Each half has 2^(N/2) sums. Sorting right and running one bisect_left for each left sum both cost an extra factor of about N/2 (the logarithm of the list size).
Why check both right[k] and right[k - 1]?: right[k] is the first sum at or above need, and right[k - 1] is the last sum below it. Either can be the nearer one. Checking only right[k] returns 4 instead of 1 on [2, 9, 1, 8] with goal = 13.
Why not use a table over sums, as in Last Stone Weight II (LC 1049)?: A table has one cell for each possible sum. That works when the values are small. In Closest Subsequence Sum (LC 1755) the values can be as large as 10^7 in absolute value, so the range of sums is far too big for a table.
What changes when the two groups must have the same size, as in LC 2035?: You group the sums of each half by how many numbers were chosen. A left sum that uses c numbers is paired only with the sorted right sums that use n - c numbers. The search step is the same, but it runs inside the matching group.
When is splitting not allowed?: When a choice in one half limits a choice in the other half in a way that a sum cannot show. Partition to K Equal Sum Subsets (LC 698) is an example, because the numbers must fill several groups in turn. Then the state is which numbers are used, and two lists of sums cannot be joined.

SWE Reasoning

Spot it

The task picks a subset or subsequence whose sum is closest to a target, or splits the numbers into two groups with the smallest difference.
N is about 30 to 40. A search over all 2^N choices is too slow, but 2^(N/2) is fine.
The values are large or negative, so a table indexed by sum is too big. That separates this card from Last Stone Weight II (LC 1049), where the sums are small.
The statement needs a best value, not one specific answer to list. A pure subset-listing task, as in Subsets (LC 78), has no sums to join.
Splitting the numbers in two does not break the rules of the problem, because a choice in one half does not limit a choice in the other half.

The invariant, step by step

Split nums at half. Every subsequence takes some numbers from nums[:half] and some from nums[half:].
all_sums starts at [0], so the empty choice is a sum of its own. A subsequence that uses only one half is still one left sum plus one right sum.
left holds every sum of the left half. right holds every sum of the right half, sorted.
For one s in left, the best partner is the sum in right closest to need = goal - s.
In a sorted list, that sum is right[k] or right[k - 1], where k = bisect_left(right, need). The code checks both, when they exist.
The loop visits every s. So best is the smallest distance over every pair of one left sum and one right sum, which means over every subsequence.

Traps

Checking only right[k]. The closest sum can be below need. On [2, 9, 1, 8] with goal = 13, the result is 4 instead of 1.
Leaving 0 out of all_sums. Then every total takes at least one number from each half. On [-4, 6] with goal = 6, the best subsequence is [6], which uses one half only. The result is 4 instead of 0.
Slicing the right half with nums[half + 1:]. Then nums[half] is in neither half and no total can use it. On [2, 9, 1, 8] with goal = 13, the result is 2 instead of 1.
Calling bisect_left before sorting right. The index it returns has no meaning, so the two neighbours are not the closest sums. On [9, -7] with goal = -7, the result is 7 instead of 0.
Starting best too low. best = abs(goal) is correct because choosing nothing gives the sum 0. A value such as 0 would hide every real result.

Practice

Canonical LeetCode:Closest Subsequence Sum (LC 1755)Partition Array Into Two Arrays to Minimize Sum Difference (LC 2035)Split Array With Same Average (LC 805)4Sum II (LC 454)