递归:理解(subset-sum)包含/排除模式

Question

我需要了解这种递归是如何工作的,我理解简单的递归示例,但更高级的示例很难.甚至认为只有两行代码我对... return声明本身有问题.我只是画了一个关于它如何工作的空白,特别是和/或运算符.任何见解都非常受欢迎.

      bool subsetSumExists(Set<int> & set, int target) {
      if (set.isEmpty()) {
         return target == 0;
      } else {
         int element = set.first();
         Set<int> rest = set - element;
         return subsetSumExists(rest, target)
             || subsetSumExists(rest, target - element);
         } 
      }

Answer 1

递归代码通常与缩减的概念相结合.通常,减少是通过某种变换将未知问题减少到已知问题的手段.

我们来看看你的代码吧.您需要查找是否可以从输入数据集的元素构造给定的目标总和.如果数据集为空,除了将目标总和与0进行比较之外,无需做任何事情.

否则,让我们应用减少.如果我们从集合中选择一个数字,实际上可能有两种可能性 - 所选择的数字参与你正在寻求的数量,或者它没有.这里没有其他可能性(涵盖所有可能性非常重要!).事实上,只要您可以涵盖剩余数据的所有可能性,选择哪个数据元素并不重要.

第一种情况:该数字不参与总和.我们可以将问题减少到一个较小的问题,数据集没有被检查的元素和相同的目标总和.

第二种情况:数字参与总和.我们可以将问题减少到较小的问题,数据集没有被检查的元素,并且请求的总和减少了数字的值.

请注意,此时您不知道这些情况是否属实.你只需继续减少它们,直到你得到一个琐碎的空案例,你可以确切地知道答案.

如果对于这两种情况中的任何一种情况都是如此,那么原始问题的答案将是正确的.这正是运算符的||作用 - 如果其任何操作数(2个案例的结果)为真,它将产生真.