Meet in the middle
Picture
Forty values create about 2⁴⁰ subsets. Splitting into two groups creates two lists of about 2²⁰ sums.
Predict
Does this make subset search polynomial?
Walk through the small example
No. Independent halves combine additively, trading one exponential exponent for two half-sized enumerations.
Mental model and complete Python solution
Every full choice is a pair of half choices. Listing both halves turns one giant search tree into two smaller catalogs that can be joined intelligently.
What the function promises: Return the minimum absolute difference between target and any subset sum. Empty subset is allowed.
from bisect import bisect_left
def closest_subset_difference(values, target):
middle = len(values)//2
def sums(part):
result = [0]
for value in part:
result += [old+value for old in result]
return result
left = sums(values[:middle])
right = sorted(sums(values[middle:]))
best = abs(target)
for subtotal in left:
position = bisect_left(right, target-subtotal)
for i in (position-1, position):
if 0 <= i < len(right):
best = min(best, abs(target-subtotal-right[i]))
return best
assert closest_subset_difference([5,-7,3,5], 6) == 0
assert closest_subset_difference([], 9) == 9
Work and storage: O(2^(n/2) · n) generation in this simple list-building form, plus sorting and O(2^(n/2)) space.
When to recognize it: Independent halves combine additively, trading one exponential exponent for two half-sized enumerations.
Check before applying it: It still grows exponentially and needs substantial memory.
Change one rule
All values are nonnegative and target is small.
See what changes
A sum-indexed DP or bitset can be pseudo-polynomial and much faster.
Connect
subset dp: Enumerate subsets, but split their interaction across two halves.
Binary search: find a boundary: Find the closest complementary right-half sum.