c++ - 使用递归方式求解子集算法给出错误答案

Question

我已经尝试解决以下问题，但仍然得到错误答案，但是问题中的两个测试用例对我来说是正确答案。

问题陈述:子集和，或简称“SS”(双 S)，是计算机科学中的经典问题。

给定一组正整数；我们必须知道这个集合是否有一个非空子集，其元素的总和等于给定的数字。

例:假设集合为[3, 4, 7, 9, 10]，目标数为20，子集[3, 7, 10]的元素之和等于20。

输入格式:输入由许多测试用例组成，每个测试用例由两行组成。在输入文件的第一行有一个数字表示测试用例的数量。每个测试用例的第一行有两个整数(k,n):k是目标数，n<=10是集合的元素数。第二行是n个整数，每个都小于一百。

输出格式:对于每个测试用例，如果存在满足上述条件的子集，则打印“YES”(不带引号)，否则打印“NO”。

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


Sample Output:
NO
YES

您可以在这里测试提交: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

我会这样做:

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);
}

其中 std::set 求和内容是给定 vector 的所有可能求和。

Live example