This lesson was originally featured at Solving the Target Sum problem with dynamic programming and more. It has been republished here with permission from Fabian Terh.

Previously, I wrote about solving the 0--1 Knapsack Problem using dynamic programming. Today, I want to discuss a similar problem: the Target Sum problem (link to LeetCode problem --- read this before continuing the rest of this article!).

The Target Sum problem is similar to the 0--1 Knapsack Problem, but with one key difference: instead of deciding whether to include an item or not, we now must decide whether to add or subtract an item. This doesn't seem like a significant difference, but it actually makes building our dynamic programming table a lot trickier.

I'll first briefly cover several more inefficient recursive solutions, before turning to the dynamic programming solutions in greater detail.