修改递归子集和 + 备忘录以打印值

Question

我正在尝试修改我的代码，解决一个叫做子集和的问题，目的是在最终返回True时打印出找到的值。现在我的实现是递归的，并且使用了记忆化技术，但我不知道怎么改动它，以便存储并最终返回一个能达到目标和的路径。

我试过放弃递归，改用循环来实现，但我不知道怎么在我的for循环中安排代码，以同时处理不使用下一个值和使用下一个值的情况。

注意：在这个实现中，值只能使用一次，不确定原始的“子集和”问题是否也有这个限制……

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]

如果能提供一些帮助或提示，告诉我怎么转换这个代码，我将非常感激。我正在做这个练习，为即将到来的面试做准备。

Answer 1

你可以在调用函数的时候使用打印功能。试着用不同的值来调用这个函数，以满足你函数里的各种条件。

比如：

print subsetSum(tot, vals, mem)

另外，你也可以在函数里面的任何地方添加打印语句，这样你就可以看到那些值了。

比如：

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]