c++ - 检查数组中的总和是否可能

Question

给定一个数组 N非负整数和 target总和，检查是否可以获得target通过选择数组的一些元素并将它们相加。 (可以多次选择一个元素)。
我试图想出一个蛮力递归解决方案。我的想法是，对于每个元素，我们有 3 个选择

包含元素并保持在同一索引中

包含元素并移动到下一个索引

排除元素并移动到下一个索引

这是我的 C++ 代码

bool checkSum(vector<int> &arr,int i, int n, int target)
{
    if(target==0)
        return true;
    if(i>=n or target<0)
        return false;

    return (checkSum(arr, i+1, n, target) or // don't include current value and move to next
            checkSum(arr, i, n, target-arr[i]) or // include current value 
            checkSum(arr, i+1, n, target-arr[i])); // include current value and move to next
}

对于某些测试用例，此代码似乎失败

arr = [10,7,0,6,2,6] target = 11   

我无法找出错误是什么。
驱动程序代码

int main()
{
    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    if (checkSum(arr, 0, n, target))
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

PS:我不是在寻找动态编程解决方案，因为我只想先做好我的基础知识。如果我能知道我在这段代码中遗漏了什么，那就太好了。

Answer 1

如果数组中有一个非正数(例如零)，您的解决方案将永远不会停止迭代。