Distinct Subset Sums
National Olympiad — Regional round
Submission name: sums.cpp
Problem summary
Choose a nonempty subset of the given positive integers, using each occurrence at most once. Count distinct resulting sum values in the inclusive interval [a,b].
Input
n a b, then n positive integers.
Output
The number of distinct attainable values in [a,b].
Constraints
Every input number is positive and strictly smaller than 100; a ≤ b.
Worked example
An independently prepared example for this explanation.
Input
4 4 8 1 3 3 10
Output
3
Solution analysis
- Maintain a Boolean reachable[s] for sums at most b, initially only sum 0.
- For every value x, scan sums downwards and set reachable[s] when reachable[s−x] is true.
- Count true entries from a through b. Positivity makes sums above b irrelevant.
Why it works
After each item the reachable set contains exactly old subsets and old subsets extended by that item. Descending updates prohibit using an item more than once. Boolean states count values, rather than subsets.
Watch out. Repeated input values represent separate usable occurrences; equal resulting sums count only once.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: After each item the reachable set contains exactly old subsets and old subsets extended by
// that item. Descending updates prohibit using an item more than once.
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int main(){
int n,a,b;
cin>>n>>a>>b;
vector<bool>can(b+1);
can[0]=true;
while(n--){
int x;
cin>>x;
for(int s=b;s>=x;s--){
can[s]=can[s]||can[s-x];
}
}
int ans=0;
for(int s=a;s<=b;s++){
ans+=can[s];
}
cout<<ans<<'\n';
}