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

- Include the element and stay in the same index
- Include the element and move to the next index
- 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++