Check if sum possible in array

  algorithm, arrays, c++, recursion

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++

LEAVE A COMMENT