Check if sum possible in array

user_13905998 0
Viewed 616

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 << "YES\n";
    else
        cout << "NO\n";

    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.

recursion arrays algorithm c++
3 Answers

The second recursion is causing the function to recurse infinitely as when arr[i] = 0, checkSum(arr, i, n, target) will call checkSum(arr, i, n, target-0) which will run infinitely.

It is senseless to add 0 more than once, so the only change required is to avoid the second recursion when arr[i] == 0

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
            (arr[i] ? checkSum(arr, i, n, target-arr[i]) : false) or // include current value 
            checkSum(arr, i+1, n, target-arr[i])); // include current value and move to next
}
user_140303530

If the array has a non-positive number (such as zero) in it, your solution will never stop iterating.

user_474530

Thanks to @BillLynch, it seems the code fails when any value is 0. So I just added an extra condition and it seems to work now.

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
            arr[i]!=0 and   // include only if non-zero value
            (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
}
user_139059980
Related