Took me longer than usual to implement this one. I could do this quicker with say, Dart. I find it difficult to elegantly implement 2D data structures with Elixir.
So here is the initial implementation of subset sum algorithm using dynamic programming. This one only says True/False as to whether a subset exists in a list that sums to a target as an example, given [1, 2, 3, 4] and target being 5 it will be true as 5 can be computed by sums of [2, 3] and [4, 1]. However, given [1, 3, 5], target of 7 should be false as no subset exists that would sum to 7
Here’s the initial implementation: ex_algo/subset_sum.ex at main · code-shoily/ex_algo · GitHub
I will attempt at a function that returns all the subsets that sum up to said target tomorrow (or tonight if I don’t get sleepy). Backtracking should be fun!
Also, this was supposed to be part of my Advent of Code reconnection through solving Year 2015/24 but felt like moving all algorithm related things into this repository instead.