Solving Subset algorithm using a recursive way gives wrong answer

Question

I have tried to solve the following problem but I still get wrong answer, however the two test cases in the problem are correct answer for me.

Problem Statement: Subsets Sum, or "SS" (double S) for shortcut, is a classical problem in computer science.

We are given a set of positive integer numbers; we have to know if there is a non-empty subset of this set that the sum of its elements is equal to a given number.

Ex: suppose the set is [3, 4, 7, 9, 10] and the target number is 20 The sum of elements of the subset [3, 7, 10] is equal to 20.

Input Format: The input consists of many test cases, each test case is composed of two lines. On the first line of the input file there is a number indicates the number of test cases. The first line of each test case has two integer numbers (k, n): k is the target number, n <= 10 is the number of elements of the set. On the second line there are n integer numbers, each of these numbers is less than one hundred.

Output Format: for each test case print "YES" without quotes if there is a subset that satisfies the condition above, "NO" otherwise.

Sample Input:
2
1 5
45 26 36 4 8 
49 8
49 9 5 37 0 42 15 19


Sample Output:
NO
YES

You can test the submission here: http://www.a2oj.com/p.jsp?ID=151

My Code:

   #include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;


bool check = false;
void get(vector<int> arr, long total, int i, int k)
{
    int length = arr.size() - 1;
    if (i == length*length || i == length)
        return;

    if (total == k)
    {
        check = true;
        return;
    }
    if (total >= k && i <= 1)
    {
        check = false;
        return;
    }
    get(arr, total + arr[i], i + 1, k);
    get(arr, total, i + 1, k);

}


int main(void) {


    int t;
    cin >> t; 

    vector<int> arr; 

    while (t--)
    {

        arr.clear();
        int n, k;
        cin >> n >> k;
        for (int i = 0; i < k; i++)
        {
            int n; 
            cin >> n;
            arr.push_back(n);
        } 

        get(arr, 0, 0, n);
    //  arr = { 49,9,5,37,0,42,15,19 };
    //  get(arr, 0, 0, 49);

        if (check)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;

        check = false;
    }

    return 0;
}

Answer 1

I have a recursive code which you could have a try,

#include <iostream>
#include <vector>

bool find_subset(const std::vector<int>& input_data, int N, int target_value)
{
    if (N == 1)
        return input_data[0] == target_value;
    bool result = false;
    for (int i = 0; i < N; ++i)
    {
        std::vector<int> copy = input_data;
        copy.erase(copy.begin() + i);
        if (input_data[i] == target_value || find_subset(copy, N - 1, target_value - input_data[i]))
        {
            result = true;
            break;
        }
    }
    return result;
}

int main()
{
    std::vector<int> test_1{45, 26, 36, 4, 8};              int target_1 = 1;
    std::vector<int> test_2{49, 9, 5, 37, 0, 42, 15, 19};   int target_2 = 49;
    std::vector<int> test_3{ 1, 3, 5, 7 };                  int target_3 = 13; 
    std::vector<int> test_4{ 1, 3, 5, 7 };                  int target_4 = 14;

    std::cout << (find_subset(test_1, test_1.size(), target_1) ? "Yes" : "No") << std::endl;
    std::cout << (find_subset(test_2, test_2.size(), target_2) ? "Yes" : "No") << std::endl;
    std::cout << (find_subset(test_3, test_3.size(), target_3) ? "Yes" : "No") << std::endl;
    std::cout << (find_subset(test_4, test_4.size(), target_4) ? "Yes" : "No") << std::endl;

    return 0;
}

The output are:

No
Yes
Yes
No

Answer 2

I would do that way:

bool SS(const std::vector<int>& v, int total)
{
    std::set<int> sums;

    for (auto e : v) {
        std::set<int> r = sums;
        r.insert(e);
        for (auto s : sums) {
            r.insert(s + e);
        }
        sums.swap(r);
    }
    return sums.count(total);
}

where the std::set sums content is all the possible sums from the given vector.

Live example

Answer 3

In the last line of your get function, you are overwriting the value computed by the previous recursive call.

get(arr, total + arr[i], i + 1, k);
get(arr, total, i + 1, k);

So if the first call sets check to true and the second one sets it to false, you will lose first one. This is one of the reasons using global variables is considered harmful, specially in recursive functions.

Instead of defining a global variable, you should change your get function to return a boolean value, and then you can have your recursive like this:

return get(arr, total + arr[i], i + 1, k) || get(arr, total, i + 1, k);

Also try to use more meaningful variable/function names. For example your recursive function can have the following prototype:

bool addsUp(vector<int> array, int total, int from, int length);

As for your k and n variables in the main function, I think you should swap their names to comply with the problem statement (k is the desired total, n is the count of numbers).

And finally your boundary conditions seem to be not quite right. This is the recursive function that got accepted for me:

bool addsUp(vector<int> arr, long soFar, int from, int total) {
    if (total == 0)
        return false;
    if (soFar == total)
        return true;
    if (soFar > total)
        return false;
    if (from >= arr.size())
        return false;
    return addsUp(arr, soFar + arr[from], from + 1, total) ||  addsUp(arr, soFar, from + 1, total);
}