java - 使用递归链接结构解决子集和问题

Question

想象一个具有整数节点(例如 5 -> 8 -> 10 -> 2 -> 7)和给定总和(例如 15)的无序单链接结构。我怎样才能找到第一个子集递归地等于总和？在此示例中，答案为 5 -> 8 -> 2(5 -> 10 或 8 -> 7 也可以是答案，但不是第一个)。我有一个方法“node f(node, sum)”:

if node == null
   return null
else if node.value <= target
   return new Node(node.item, f(node.next, sum - node.value)
else
   return f(node.next, sum)

但是，这将返回小于或等于总和的子集，而不是精确的总和。如何创建精确的算法？

Answer 1

Backtrack就是您正在寻找的。 :)

此外，您还没有定义子集的排序方式。依靠这种回溯并在找到解决方案后停止可能行不通，您将必须实现 BFS可能的解决方案。