Introduction to Meet in the Middle

You are given 40 numbers and a target. Is there any subset of them that sums to the target?

[3, 34, 4, 12, 5, 2]   target 9      yes:  4 + 5

Every element is either in the subset or out of it, so there are 2^N subsets. For 40 elements that is about a trillion, which will not finish.

Splitting the list in half changes the arithmetic completely. Each half has 20 elements, so each has about a million subsets. Two million is small.

But the answer needs a whole subset, and a subset can take elements from both halves