Module Introduction to meet in the middle

Introduction to meet in the middle

**Frequency: 1/10** This technique divides the search space into two. This technique can improve naive backtracking, help to solve problems with higher constraint (for example $n=40$ instead of $20$). May appear as a subtask in OI style contest.

Resources

- [USACO Guide: Meet in the middle](https://usaco.guide/gold/meet-in-the-middle)

Problems

Subset sum 2 195 / 239 800
Sum of four values 123 / 149 800
Robot 109 / 121 900
Minimum difference 104 / 142 900
Maximum sum subset 81 / 102 1000
Stealing books 88 / 99 1000