Modify Recursive Subset Sum + Memoize to print values

Question

I'm trying to figure out how I can modify my code for the subset sum problem so that I can print out the values it found when it ultimately returns True. My current implementation works recursively and utilizes memoization, but I can't figure out how to alter it to store and eventually return a path that reaches the desired sum.

I've tried scrapping the recursiveness of it and using iteration instead, but I can't figure out how to lay out the code within my for loops to handle both the case where we DON'T use the next value and when we DO use it.

NOTE: in this implementation, values can only be used once, not sure if the origin "subset sum" problem enforces that or not...

def subsetSum(tot, vals, mem={}):
  key = (tot, len(vals))
  if key not in mem:
    if tot == 0:
      mem[key] = True
      return True
    if tot < 0 or len(vals) == 0:
      mem[key] = False
      return False
    return subsetSum(tot, vals[:-1], mem) or 
           subsetSum(tot-vals[-1], vals[:-1], mem)
  else:
    return mem[key]

Any help or hints as to how to convert this would be greatly appreciated. I'm doing this as practice for upcoming interviews.

Answer 1

You can use print while calling the function. Try calling the function with different values to satify various conditions in your function.

For example:

print subsetSum(tot, vals, mem)

Alternatively you can add print statements in the function wherever you want to see the value.

For example:

def subsetSum(tot, vals, mem={}):
  key = (tot, len(vals))
  if key not in mem:
    if tot == 0:
      mem[key] = True
      return True
    if tot < 0 or len(vals) == 0:
       print tot, len(vals)   #Added a print statement here
       mem[key] = False
       return False
    return subsetSum(tot, vals[:-1], mem) or 
           subsetSum(tot-vals[-1], vals[:-1], mem)
  else:
    return mem[key]