#### Check if sum possible in array

Given an array of `N` nonnegative integers and a `target` sum, check if it is possible to obtain `target` by choosing some elements of the array and adding them up. (An element can be chosen multiple times).

I tried to come up with a brute force recursive solution. My idea is that for each element, we have 3 choices

1. Include the element and stay in the same index
2. Include the element and move to the next index
3. Exclude the element and move to the next index

Here’s my C++ code

``````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
}
``````

This code seems to fail for some testcases

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

I am not able to find out what is the bug.

Driver Code

``````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 << "YESn";
else
cout << "NOn";

return 0;
}
``````

PS: I am not looking for Dynamic Programming solutions as I just want to make my basics right first. It would be nice if I can know what I am missing in this code.

Source: Windows Questions C++