1

我试图弄清楚如何修改子集和问题的代码，以便我可以打印出它最终返回 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]

任何有关如何转换它的帮助或提示将不胜感激。我这样做是为了为即将到来的面试做练习。

4

1 回答 1

1

您可以在调用函数时使用 print。尝试使用不同的值调用函数来满足函数中的各种条件。

例如：

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]
于 2014-03-09T02:46:12.253 回答