Mike is a very passionate about sets. Lately, he is busy solving one of the problems on sets. He has to find whether if the sum of any of the non-empty subsets of the set A is zero.
Input Format
The first line contains an integer T, which is the total number of test cases.
T test cases follow.
Each test case consists of two lines.
The first line consists of a single integer N, which is the number of elements present in the set A.
The second line contains N space separated integers denoting the elements of the set A.
The code:
#include
#include
using namespace std;
bool sumZeroOrNot(const vector& input, int i, int currentSum) {
if (i == input.size()) {
return currentSum == 0;
}
return sumZeroOrNot(input, i + 1, currentSum + input[i]) || sumZeroOrNot(input, i + 1, currentSum);
}
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> v(n);
for (int j = 0; j < n; j++) {
cin >> v[j];
}
if (sumZeroOrNot(v, 0, 0)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}