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

Question

给定一个N非负整数数组和一个target和，检查是否可以target通过选择数组中的一些元素并将它们相加来获得。（可以多次选择一个元素）。

我试图想出一个蛮力递归解决方案。我的想法是，对于每个元素，我们有 3 个选择

1. 包含元素并保持在同一个索引中
2. 包含元素并移动到下一个索引
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：我不是在寻找动态编程解决方案，因为我只想先做好我的基础。如果我能知道我在这段代码中缺少什么，那就太好了。

标签： c++arraysalgorithmrecursion

Answer 1

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