Subset Sum Algorithm Optimization and Parallelization

Subset Sum Algorithm Optimization and Parallelization

Optimization and thread-based parallelization of algorithms that count subsets whose elements sum to a specified value.

QR code for this page

A counter is incremented whenever the sum of the elements of a subset equals the specified integer value.

Different algorithms for this problem were researched and optimized.

The `Giris()` function creates the array.

The `Basla()` function prints a heading according to the string parameter and starts the timer.

The `Bitir()` function stops the timer and prints the elapsed time and result.

For an array with `n = 23` elements, the number of subsets is `m = 2^23 = 8,388,608`.

The target sum was set to `200`.

Under these conditions, the number of matching subsets was `17,891`.

The results showed that dynamic programming ran much faster than the other evaluated algorithms. The parallel implementation also reduced execution time to one fifth of its previous value.