3

这是从给定集合和目标值中获取真假的解决方案之一

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

但是，此解决方案将仅返回 true 或 false 值。怎么可能得到涉及子集的元素（加在一起的集合等于目标）？

我必须使用动态编程吗？因为我知道..递归实际上是在建立堆栈，在函数返回值之后，框架内的值也将被丢弃。

那么，是否有可能获得加起来等于目标值的元素。

传递对象是问题的解决方案吗？

谢谢

4

1 回答 1

5

首先，您可以稍微优化一下您的程序——检查目标是否是0以及它是否总是返回true。现在你需要的是有一个地方来存储你已经使用过的元素。我将向您展示一种使用全局“堆栈”的方法（vector实际上这样您就可以对其进行迭代），因为这样代码将更容易理解，但您也可以通过引用函数来传递它或避免以其他方式使其全球化。顺便说一下 stl 容器被称为setnot Set。

vector<int> used;
bool subsetSumExists(Set<int> & set, int target) {
    if (target == 0) {
        cout << "One possible sum is:\n";
        for (int i = 0; i < used.size(); ++i) {
          cout << used[i] << endl;
        }
        return true;
    } else if(set.empty()) {
      return false;
    }else {
        int element = set.first();
        Set<int> rest = set - element;
        used.push_back(element);
        if (subsetSumExists(rest, target- element)) {
          return true;
        } else {
          used.pop_back();
        }
        return subsetSumExists(rest, target);
    }
}

希望这可以帮助。

于 2012-04-06T06:16:11.333 回答