Distinct nonempty subsequence sums
National Olympiad — Regional round
Submission name: subsums.cpp
Problem summary
For every nonempty subsequence of the given array, compute the sum of its elements. Count the distinct resulting sums. A subsequence may skip positions; it need not be contiguous.
Input
N, then N integers.
Output
The number of distinct sums.
Constraints
1 < N < 1000; −1000 ≤ a[i] ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
3 2 -2 2
Output
4
Solution analysis
- A bitset represents sums from −1,000,000 to 1,000,000 using a fixed offset. Start with no attainable nonempty sum.
- For each x retain old sums, shift old sums by x to append x, and insert the singleton sum x.
- Count set bits. This explicitly excludes the empty subsequence while retaining zero when achieved nontrivially.
Why it works
Every nonempty subsequence either omits the current element, consists of it alone, or appends it to an earlier nonempty subsequence. The union transition is exact.
Complexity: O(N·S/w) word operations and O(S) bits, S=2,000,001 and machine word size w.
Watch out. Zero must not be counted solely because the empty subsequence exists. Repeated equal sums count once.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every nonempty subsequence either omits the current element, consists of it alone, or
// appends it to an earlier nonempty subsequence. The union transition is exact.
#include<iostream>
#include<algorithm>
#include<set>
#include<bitset>
using namespace std;
int main(){
int n;
cin>>n;
const int O=1000000;
bitset<2000001>b;
while(n--){
int x;
cin>>x;
if(x>=0){
b|=b<<x;
}
else{
b|=b>>(-x);
}
b.set(O+x);
}
cout<<b.count()<<'\n';
}