CODEWITHSUNDEEP
c++algorithmc++11c++14
Rockstar5645
Rockstar5645

Reputation: 4518

How to find size of largest subset of a sub-sequence equal to a sum

I have this problem from hackerearth

Given an array of N integers, C cards and S sum. Each card can be used either to increment or decrement an integer in the given array by 1. Find if there is any subset (after/before using any no.of cards) with sum S in the given array.

Input Format

First line of input contains an integer T which denotes the no. of testcases. Each test case has 2 lines of input. First line of each test case has three integers N(size of the array), S(subset sum) and C(no. of cards). Second line of each test case has N integers of the array(a1 to aN) seperated by a space.

Constraints

1<=T<=100
1<=N<=100
1<=S<=10000
0<=C<=100
1<=ai<=100

Output Format

Print TRUE if there exists a subset with given sum else print FALSE.

So this is basically a variation of the subset sum problem, but instead of finding out whether a given subset with a sum S exists, we need to find the largest subset from sequence index to N-1 that has a value of s and compare it's length with our C value to see if it is greater. If it is, then we have enough elements to modify the sum using our C cards, and then we print out our answer. Here is my code for that

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

So basically, 0 means it's not possible to create a subset equal to s from elements index to N-1, and -1 means we haven't computed it yet. And any other value indicates the size of the largest subset that sums up to s. This code isn't passing all the test cases. What's wrong?

Upvotes: 2

Views: 699

Answers (2)

hk6279
hk6279

Reputation: 1879

You miss an else in following line

} if (newSum > 0) {

This make your program has an unexpected early break before updating maxNums by l in some cases.

For example, N=1, S=5, C=0, a={5}

Potential logic problem

You have limited the no. of card to be used to not exceed the subset size while the question never state you cannot apply multiple cards to same integers.

I mean l >= i and m >= i in

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

Upvotes: 1

MBo
MBo

Reputation: 80197

Seems you have logic flaw.

You need to find the shortest subset (with sum in range S-C..S+C) and compare it's size with C. If subset is shorter, it is possible to make needed sum.

Upvotes: 0

Related Questions