#include
using namespace std;
bool Subset_Sum(int *A,int i,int j,int n)
{
if(i==n-1)
{
return false;;
}
if(j==n)
return Subset_Sum(A,i+1,0,n);
if(A[i]+A[j]==0)
return true;
else
return Subset_Sum(A,i,j+1,n);
}
int main()
{
int t,n;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
int *A=new int[n];
for(int i=0;i<n;i++)
cin>>A[i];
if(Subset_Sum(A,0,1,n))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
hi @Mukul-Shane-1247687648773500,
logic is incorrect
u r considering any 2 element at a time even more than 2 elements can sum upto 0
1
4
4 -1 -1 -2 here ans is yes all elements sum to 0 but your logic will give wrong ans
At each step during the recursion , we make a call once where we include the current element into our sum and another where we exclude. If at the end when we reach the end of the array , we have obtained the sum=0, we return true , else false. During the intermediate recursive calls , we check the result from both the recursive calls , one including the current element and one excluding and return their OR since even if one of them had the subset sum 0 then we have to return true.
Note that the NULL subset ( subset with no elements ) is not to be considered as that would always have sum 0. To avoid considering that , we take a flag variable bool included = false and mark it as true even if we include a single element. Else it remains false. The NULL subset would be the only subset where the flag would remain false. For all other subsets , they would have included atleast one element and hence their flag would be true.
for implementation difficulties refer to the code https://ide.codingblocks.com/s/660299