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 200 / 245 800
Sum of four values 126 / 152 800
Robot 110 / 123 900
Minimum difference 105 / 145 900
Maximum sum subset 84 / 106 1000
Stealing books 88 / 99 1000