How can I memoize this subset sum algorithm?

Question

This is not the same as this question: find all subsets that sum to a particular value As I don't just have to count the total number of subsets, but store all the subsets and return it.

I wrote a simple (exponential) algorithm that finds subsets summing up to a particular target:

Eg:
arr = [1,2,3,4,5,6,7,8]
Possible subsets:
5
4,1
3,2

This is my algorithm

n -> index of list (starts from the end)

target -> sum of subsets I want to create

arr = [1,2,3,4,5,6,7,8]
def subset_sum(arr, n, target, result):

    if target == 0:
        print result
        return

    if target < 0 or n < 0:
        return False



    subset_sum(arr, n-1, target - arr[n], result + str(arr[n]))
    subset_sum(arr, n - 1, target, result)

print subset_sum(arr, len(arr) - 1, 5, '' )

I wish to opmitize this, possibly by memoization. But I am having hard time figuring out what should be the state of this function (Should it be n and target?.. but I don't see it being repeated )

What is a previously computed result for `subset_sum(n)`? `subset_sum(n-1)`. It seems reasonable to store all the subsets that sum up to each `n-1`. — Michael Foukarakis, Dec 02 '16 at 15:54
Yea, but I don't know how to store the result (subset numbers) in a cache. I wish to memoize it in top down manner. — yask, Dec 02 '16 at 15:57
When you say you don't know how to store it, you have to be more specific about what the problem is. Are you completely unaware of available data structures, or are you having trouble with choosing one? Why not pick one and do some preliminary analysis? — Michael Foukarakis, Dec 02 '16 at 16:10
Possible duplicate of [find all subsets that sum to a particular value](http://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value) — Nick Zuber, Dec 02 '16 at 16:16
@MichaelFoukarakis I meant I don't know how to store the pre-cache result (which might contain more than one result) in the cache dictionary. Usually cache[n] stores True or False which means if its possible to reach the solution from state n or not. Also, n isn't the unique state of this function here: It's probably the compination of `n` and `target` which can be used as a unique state to cache the result. — yask, Dec 02 '16 at 16:21

score 2 · Accepted Answer · edited Jan 31 '22 at 00:26

"I don't see it being repeated."

Consider a simple example of an array having duplicate values or zeros.
e.g. arr = [3,2,4,5,0,5], and you are looking for subsets that sum to 7, See here that the index 3(if start index is 1), is hit with resultant 2 twice, once when the last 5 is included in the answer and again when it is excluded from answer
For more clarity, look here for another example
arr = [5,2,3,6,3,5,8], you are looking for sum 12, you pick the last index i.e. 7, and leave 6,5 hence reaching index 4 with sum 4, or you leave index 7 and pick index 6,5 and again reach index 4 with sum 4.
So here is the need for memoization.
You can also solve the problem n bottom-up fashion by building a matrix of n rows and sum columns, or vice versa.

How can I memoize this subset sum algorithm?

1 Answers1