Getting wrong answer for subset sum easy

#1

My sample test cases got passed but it is showing wrong answer.Here’s my code
#include<bits/stdc++.h>
using namespace std;
int subsetSum(int arr[],int i,int n,int sum){
if((i==n)){
if((sum>0))
return 0;
else{
return 1;
}
}
return subsetSum(arr,i+1,n,sum);
return subsetSum(arr,i+1,n,sum+arr[i]);
}

int main() {
int t;
cin>>t;
int n;
while(t–){
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int flg=0;

    if(subsetSum(arr,0,n,0)){
        cout<<"Yes\n";
    }       
    else{
        cout<<"No\n";
    }
}
return 0;

}

#2

Hello @aman.tandon3096,

Let’s your code will always return 1 irrespective of the test case.
Reasons:

  1. The statement 1.2 will never execute. When the control will come to statement 1.1., it will return from the function after executing it and hence, further statements in the function will not be executed.
    1.1. return subsetSum(arr,i+1,n,sum);
    1.2. return subsetSum(arr,i+1,n,sum+arr[i]);
    Solution:
    return (subsetSum(arr,i+1,n,sum) || subsetSum(arr,i+1,n,sum+arr[i]));
    if any one of them is true then return true i.e. a subset exists for which the sum is zero.

  2. As you are passing sum as 0, in the case of an empty subset the sum will remain 0.
    Because you have not added any element to it.
    So, your code will return 1 for that.
    Solution:
    Try to think.

Let me know if you do not understand.

Hope, this would help.
Give a like if you are satisfied.

#3

if I m doing or statement in recursive case then there is never ending loop. Also could not get your 2nd point

#4

Hey @aman.tandon3096,

Why do you think so?
if I m doing or statement in recursive case then there is never ending loop.
It won’t lead to infinite recursive calls.
As your recursion will terminate when i becomes equal to n.
And as you are incrementing the value of i for each recursive calls.
So, base condition will surely execute.

And my second point says:
As your recursive function is creating of the subsets of the given array.

  1. By not considering the current element in the subset.
  2. By considering the current element in the subset.
    Example:
    for array={1, 2, 3}, the subsets would be
    {} //Empty subset
    {1}
    {2}
    {3}
    {1, 2}
    {1, 3}
    {2, 3}
    {1, 2, 3}
    As you are passing sum as 0 in the function i.e. subsetSum(arr,0,n,0),
    the base condition will return 1 for empty subset.

Suggestion:
Try to dry run your code using pen and paper to better understand the flow of your code.

Refer to the code below for the for better understanding.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.