我正在练习递归和尝试小问题。我尝试设计的函数之一 comboSum
接受一个整数数组、它的大小和一个目标值。如果任何元素的组合(每个元素只能使用一次)添加到目标值,它返回 true。到目前为止,这是我的实现。
// Expected Behaviors
// comboSum([1, 2, 3], 3, 0) => false
// comboSum([2, 4, 8], 3, 12) => true
// comboSum([2, 4, 8], 3, 11) => false
// comboSum([], 0, 0) => true
bool comboSum(const int a[], int size, int target)
{
if (target == 0)
return true; // if we have decremented target to zero
if (target != 0 && size == 0)
return false; // if we havent hit target to zero and we have no more elements
size--;
return (comboSum(a, size, target) || comboSum(a, size, target - a[size]));
// OR logic ensures that even if just one sum exists, this returns true
}
我的算法有效,但数组具有所有非零值且目标为零的情况除外。该函数立即返回 true,而不检查有效的求和。
// comboSum({1, 2, 3}, 3, 0) returns true when this should be false
有哪些可能的方法可以解决此问题?
编辑:我无法更改参数或调用任何其他辅助函数。函数头必须保持原样,我必须递归地解决问题(不使用 for 或 while 循环或 STL 算法)
最佳答案
一个简单的解决方案是保持 size
参数固定,并有另一个参数指示递归的当前位置。
bool comboSum(const int *a, int size, int pos, int target) {
if (target == 0)
return pos < size || size == 0; // true if pos has moved or if the array is empty
else if (pos == 0)
return false;
pos--;
return comboSum(a, size, pos, target) || comboSum(a, size, pos, target - a[pos]);
}
此解决方案可以正确处理您的测试用例,但我们必须在 size
参数之后传递 pos
参数。两个参数应以相同的值开头:
// comboSum([1, 2, 3], 3, 3, 0) => false
// comboSum([2, 4, 8], 3, 3, 12) => true
// comboSum([2, 4, 8], 3, 3, 11) => false
// comboSum([], 0, 0, 0) => true
C++ 实践
由于此问题被标记为 C++,因此最好使用一个比 C 数组更灵活的类。例如,我们可以使用 std::vector
。如果是这样,那么我们就不需要额外的列表大小参数:
#include <vector>
bool comboSum(std::vector<int>& v, size_t pos, int target)
{
if (target == 0) {
return pos < v.size() || v.size() == 0;
} else if (pos == 0) {
return false;
}
pos--;
return comboSum(v, pos, target) || comboSum(v, size, target - v[pos]);
}
关于c++ - 递归确定数组中的元素是否可以求和到目标 - C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51577015/