c++ - 递归:理解(子集和)包含/排除模式

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 种可能性 - 所选数字参与您正在寻找的总和，或者不参与。这里没有其他可能性(涵盖所有可能性非常重要!)。事实上，选择哪个数据元素并不重要，只要您能够涵盖剩余数据的所有可能性即可。

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

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

请注意，此时您不知道这些情况是否属实。您只需继续减少它们，直到您到达可以确定答案的微不足道的空案例。

如果这两种情况中的任何一种都为真，则原始问题的答案为真。这正是运算符 || 所做的 - 如果它的任何操作数(两种情况的结果)为真，它将产生真。