Subset Sum Algorithm Optimization and Parallelization
An optimization project comparing exhaustive subset enumeration, dynamic programming and thread-based parallelism for counting subsets whose values match a target sum.
This project compared several ways of finding and counting subsets whose values add up to a target integer.
In the historical test, n = 23 elements produced:
2^23 = 8,388,608possible subsets. With a target sum of 200, the surviving project record reports 17,891 matching subsets.
Exhaustive Search
Generating every subset provides a direct solution, but the search space grows exponentially with the number of elements. Increasing n by only a few values can therefore multiply the work substantially.
The project became an early example of why optimizing the inner loop is often less important than removing repeated states from the algorithm.
Dynamic Programming
For suitable input values and target ranges, dynamic programming can track reachable sums or the number of ways to reach each sum instead of explicitly generating every subset.
Its cost becomes pseudo-polynomial in the target range rather than simply 2^n. That distinction matters: target magnitude and value domain are part of the complexity model.
I therefore do not generalize the historical result into "dynamic programming is always fast for Subset Sum." It was much faster for the test configuration used in this project.
Parallel Execution
Independent parts of an exhaustive search can be partitioned across threads. The original project record states that the parallel version reduced elapsed time to about one fifth under the tested conditions.
The recorded approximately 5x improvement belongs to that specific test setup. Core count, work partitioning, synchronization and memory behavior would all be required before treating it as a hardware-independent scaling result.
Benchmarking Perspective
The original application used shared start/finish helpers for elapsed-time measurement. A repeatable benchmark also requires controlled warm-up, repetition count, input copies, background load and a distribution of measured times.
The broader algorithmic background is covered in Data Structures and Algorithm Analysis.
