子集和重叠难题递归 [英] Subset sum overlapping dilemma recursively

问题描述

我正在研究递归逻辑，问题之一是子集和. AFAI读取，通过递归运行时有重叠.但是，我不知道怎么回事.另外，我读到要克服这个问题，可以使用DP，但是我想理解 递归如何克服这个问题. 您能想象一个重叠的例子吗?

I'm studying recursive logic that one of the problems is subset sum. AFAI read, there are overlaps when it is run by recursion. But, I cannot figure out how there are. Also, I read that to overcome the issue DP can be used but I want to comprehend how the recursion overcome the problem. Could you picturize an example with overlapping?

伪代码

def hasSum( array, start, sum):
   if sum == 0:
       return true

   if start > array.length - 1:
       return false;

   return hasSum(array, start + 1, sum - array[start])
           or hasSum(array, start + 1, sum)

我无法将逻辑与下图相关联，我肯定忽略了一个或多个点.

I cannot associate the logic with the following picture, I'm certainly overlook a point / points.

推荐答案

此行在此处引起重叠:

return hasSum(array, start + 1, sum - array[start])
           or hasSum(array, start + 1, sum)

如果算法没有在第一个hasSum中找到有效条件(由于递归已经在整个数组中进行了递归，因此返回到此点)，它将使用第二个会忽略此当前索引的值.这意味着该算法会多次检查相同的索引.

If the algorithm doesn't find a valid condition with the first hasSum (which because of recursion has already gone through the entire array by the time is returns to this point), it will try again with the second hasSum which ignores the value of this current index. This means that the algorithm checks the same indexes multiple times.

这篇关于子集和重叠难题递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！