Small Implementation: Subset Sum

Classic subproblem: is there a subset with a given sum? Decide for each element: take it or leave it.

Equal-sum partition: Partition Equal Subset Sum [1].

$$\sum_i x_i a_i = t,\quad x_i\in\{0,1\}$$

Where used

Knapsack-related problems, Target-Sum in pipelines, teaching bridge to DP: first complete search, then memoization of the same states.

Depth

In the subset sum problem, the recursion decides for each element between including or skipping it. A compact state consists of the index and the remaining required sum. Two different selection paths can reach the same state pair, which is why memoization eliminates many repetitions.

With only non-negative numbers, a negative remainder can be considered unsuccessful. With negative inputs, this cut is uncertain because later values could offset the remainder. The correctness of an optimization thus depends on the guaranteed input properties.

Difficulty levels

1. Execute the two recursive cases for a small list.
2. Derive safe termination conditions from the value range.
3. Use index and remaining sum as memoization keys.

Pitfalls

Anyone who only memoizes based on the remaining sum mixes states with different still available elements. Additionally, the empty subset candidate for the target sum zero must be treated explicitly.