递归:理解(子集总和)包含/排除模式 [英] Recursion: Understanding (subset-sum) inclusion/exclusion pattern

问题描述

我需要了解这种递归是如何工作的，我了解简单的递归示例，但更高级的示例很难.甚至认为只有两行代码我遇到了问题...... return 语句本身.我只是对它是如何工作的，尤其是和/或操作符的空白.非常欢迎任何见解.

I need to understand how this recursion work, I understand simple recursion examples but more advanced ones is hard. Even thought there are just two lines of code I got problem with... the return statement itself. I just draw a blank on how this works, especially the and/or operator. Any insight is very welcome.

      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);
         } 
      }

推荐答案

要理解递归，你需要理解递归.为此，您需要反复思考.

To understand recursion, you need to understrand recursion. To do that, you need to think recusively.

在这种特殊情况下.

对于任何:subsetSum(set, target)

1. 如果set为空且target为0，则subsetSum存在

否则，删除 set 的第一个元素.检查 subdetSum(set, target) 是否存在或 subdetSum(set, target - removed_element) 存在(使用步骤 0)

Otherwise, remove first element of the set. check if subdetSum(set, target) exists OR subdetSum(set, target - removed_element) exists (using step 0)

这篇关于递归:理解(子集总和)包含/排除模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！