Prüfen Sie, ob eine Zielsumme bei gegebenem Wertevektor möglich ist ⇐ C++

[Guest]

Das Problem besteht darin, zu prüfen, ob es möglich ist, eine bestimmte Zielsumme aus den Elementen eines bestimmten Arrays zu erhalten. Jedes Element sollte nur einmal enthalten sein (sofern enthalten).
Der Code ist ein Brute-Force-Ansatz mit Rekursion. Ich wollte die Idee umsetzen, dass true zurückgegeben wird, wenn das aktuelle Element die Summe gleich targetSum macht. Wenn das aktuelle, zu currSum hinzugefügte Element kleiner als targetSum ist, prüfen Sie, ob die Einbeziehung des Elements „true“ zurückgibt. Wenn ja, gebe ich true zurück, andernfalls überprüfe ich, ohne es in currSum aufzunehmen.
Die Sache ist, dass das Programm für einige Vektoren eine korrekte Antwort gibt, und a Falsche Antwort für einige andere Vektoren.
Die rekursive Funktion:

Code: Select all

bool checkSum(vector 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;
}

Für diese Eingabe:

Code: Select all

v : [ 4 18 5 9 ]
targetSum : 14

Die Ausgabe ist falsch.
Für diese Eingabe:

Code: Select all

v : [ 4 11 5 9 ]
targetSum : 14

Die Ausgabe ist wahr.
Ich kann nicht herausfinden, was hier möglicherweise schief läuft.
Der Treibercode:

Code: Select all

int main(){
int n;
cin>>n;
vector v(n);
for(auto &it:v){
cin>>it;
}
int targetSum;
cin>>targetSum;
cout