< Back to forum

i am not identifying my mistake , since giving correct output on codeblocks but not accepted

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long int t,n,d,a[100],sum=0,p=0,i;
    cin>>t;
    while(t--){
        cin>>n>>d;
        for(i=0;i<n;i++)
            cin>>a[i];
            sort(a,a+n,greater<int>());
        for(i=0;i<n;i++){
            sum=sum+a[i];
            if(sum==d){
                p=1;
                break;
            }
            else if(sum>d){
                sum=sum-a[i];
            }
            else
                sum=sum;
        }
        if(p==0)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
        p=0;
        sum=0;
    }
}

 

Asked by: Deepak_kumar_Shaw on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.


Enter your answer details below:


Preview

Enter your comment details below:

Preview




1 Answer(s)

avatar

Your code fails for the following test case:

3 7

3

7

Correct Output : Yes

You are assuming that notes of value lower than the required value will always be included. But, this may not be the case as in the above test case we can make 7 without including 1 and 3.

The idea here is to generate all the possible combinations of notes and check whether there exists any such combination in which the sum of notes is equal to the sum required. In the above test case total combinations possible will be 2^3 :

NIL

1

3

7

1 3

1 7

3 7

1 3 7

Out of which the correct answer is the 4th combination. So, try generating all subsets and find its sum. If any sum is equal to required sum then output will be yes else no.

Refer to this link to know more about subset generation : https://www.geeksforgeeks.org/print-sums-subsets-given-set/

 

Chetan_Garg last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.