检查给定值向量是否可以得到目标总和

Question

问题是检查是否可以从给定数组的元素中获取给定的

targetSum

。每个元素只能包含一次（如果包含）。

该代码是使用递归的强力方法。我想实现这样的想法：如果当前元素使总和等于

targetSum

，则返回 true。如果添加到

currSum

的当前元素小于

targetSum

，则检查包含它是否返回 true。如果是，我将返回true，否则我将检查而不将其包含在

currSum

中。

问题是，程序对某些向量给出了正确的答案，而对其他一些向量给出了错误的答案。

递归函数：

bool checkSum(vector<int> v, int idx, int currSum, int targetSum){
    if(idx == v.size()) return false;
    if(currSum+v[idx] == targetSum) return true;
    if(currSum+v[idx] > targetSum) return false;
    bool ans = checkSum(v, idx+1, currSum+v[idx], targetSum);
    if(ans) return true;
    ans = checkSum(v, idx+1, currSum, targetSum);
    return ans;
}

对于此输入：

v : [ 4 18 5 9 ]
targetSum : 14

输出为假。

对于此输入：

v : [ 4 11 5 9 ]
targetSum : 14

输出为真。

我不知道这里可能出了什么问题。

驱动程序代码：

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(auto &it:v){
        cin>>it;
    }
    int targetSum;
    cin>>targetSum;
    cout<<(checkSum(v,0,0,targetSum)?"true":"false");
}

Answer 1

即使当前数字大于总和，您也需要继续检查向量的其余部分。

bool checkSum(vector<int> v, int idx, int currSum, int targetSum){
    if(idx == v.size()) return false;
    if(currSum+v[idx] == targetSum) return true;
    if(currSum+v[idx] > targetSum) return checkSum(v, idx+1, currSum, targetSum);
    bool ans = checkSum(v, idx+1, currSum+v[idx], targetSum);
    if(ans) return true;
    ans = checkSum(v, idx+1, currSum, targetSum);
    return ans;
}