如何求子序列中等于和最大子集的大小

Question

我有这个问题来自hackerearth

给定一个N个整数的数组，C个卡和S个和。每一张卡片都可以用来将给定数组中的一个整数递增或递减1。查找给定数组中是否有任何子集（在使用任意数量的卡之后/之前）具有和S。

输入格式

输出格式

如果存在具有给定和的子集，则打印TRUE，否则打印false。

所以这基本上是子集和问题的一种变体，但我们不是要找出一个给定的具有和s的子集是否存在，而是要找到从序列index到n-1中最大的子集，它的值为s并将它的长度与我们的c的值进行比较，看看它是否更大。如果是，那么我们就有足够的元素来使用c卡修改和，然后打印出我们的答案。这是我的代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, S, C;


int checkSum(int index, int s, vector<int>& a, vector< vector<int> >& dP) {

    if (dP[index][s] != -1)
        return dP[index][s];

    int maxNums = 0;    // size of maximum subset array

    for (int i = index; i < N; i++) {

        int newSum = s - a[i];
        int l = 0;

        if (newSum == 0) {
            l = 1;
        } if (newSum > 0) {

            if (i < (N-1)) {    // only if we can still fill up sum
                l = checkSum(i + 1, newSum, a, dP);

                if (l > 0)      // if it is possible to create this sum
                    l++;        // include l in it
            } else {
                // l stays at 0 for there is no subset that can create this sum
            }

        } else {
            // there is no way to create this sum, including this number, so skip it;
            if (i == (N-1))
                break;      // don't go to the next level

            // and l stays at 0
        }

        if (l > maxNums) {
            maxNums = l;
        }
    }

    dP[index][s] = maxNums;
    return maxNums;
}


int main() {

    int t;
    cin >> t;

    while (t--) {
        cin >> N >> S >> C;
        vector<int> a(N);

        for (int i = 0; i < N; i++)
            cin >> a[i];

        vector< vector<int> > dP(N, vector<int>(S + C + 2, -1));

        bool possible = false;

        for (int i = 0; i <= C; i++) {
            int l = checkSum(0, S-i, a, dP);
            int m = checkSum(0, S+i, a, dP);

            if ( (l > 0 && l >= i) || (m > 0 && m >= i) ) {

                cout << "TRUE" << endl;
                possible = true;
                break;
            }

        }

        if (!possible)
            cout << "FALSE" << endl;
    }

    return 0;
}

所以基本上，0意味着不可能创建一个从元素索引到N-1的等于s的子集，-1意味着我们还没有计算它。而任何其他值则表示最大子集的大小,该子集加起来为s。这段代码没有通过所有的测试用例。怎么了？

Answer 1

下一行中缺少else

} if (newSum > 0) {

在某些情况下，这会使程序在按l更新maxnums之前出现意外的提前中断。

例如,n=1,s=5,c=0,a={5}

if ( (l > 0 && l >= i) || (m > 0 && m >= i) ) {