Проверьте, возможна ли целевая сумма с учетом вектора значений ⇐ C++

[Anonymous]

Проблема состоит в том, чтобы проверить, возможно ли получить заданную цель из элементов данного массива. Каждый элемент должен быть включен только один раз (если включен). < /P>
Код является подходом грубой силы с использованием рекурсии. Я хотел реализовать идею, что если текущий элемент делает сумму равной Targetsum , то верните True. Если текущий элемент, добавленный в Currsum меньше, чем targetsum , то проверьте, возвращает ли он true. Если это произойдет, я верну true, в противном случае я проверю, не включив его в Currsum .
Дело в том, что программа дает правильный ответ для некоторых векторов, а Неправильный ответ для некоторых других векторов. < /p>
Рекурсивная функция: < /p>
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;
}
< /code>
Для этого ввода: < /p>
v : [ 4 18 5 9 ]
targetSum : 14
< /code>
Выход False. < /p>
Для этого ввода: < /p>
v : [ 4 11 5 9 ]
targetSum : 14
< /code>
Вывод верен. < /p>
Я не могу понять, что может пойти не так. > Код драйвера: < /p>
int main(){
int n;
cin>>n;
vector v(n);
for(auto &it:v){
cin>>it;
}
int targetSum;
cin>>targetSum;
cout

Подробнее здесь: https://stackoverflow.com/questions/793 ... -of-values