Count and Reconstruct Subset Sums
Autumn Tournament (2024)
Submission name: sums.cpp
Problem summary
For distinct positive values, count the different nonempty subset sums. Find the sum with most representations, breaking ties toward the largest sum, and output its lexicographically smallest increasing list of summands.
Input
n, then n distinct positive integers.
Output
Three lines: number of sums; chosen sum and its number of representations; lexicographically smallest increasing representation.
Constraints
2 ≤ n ≤ 70; 1 ≤ ai ≤ 1000; every requested output number is less than5·10^18.
Worked example
Original statement sample.
Input
4 1 3 4 6
Output
12 10 2 1 3 6
Solution analysis
- Sort the values. A descending 0/1-knapsack update counts subsets for every sum: ways[0]=1 and ways[s]+=ways[s−x] for each value x. Descending order prevents reusing a value. Count positive sums with nonzero ways, and choose the largest sum among those with maximum ways.
- For reconstruction, compute suffix reachability: can[i][s] says whether values from index i onward can form s. Start with can[n][0]=true and fill rows backward. At each sorted value x, include it whenever the remaining sum minus x is attainable with later values; otherwise skip it.
- The sample has12 distinct nonempty sums. Sums4,7,10 each have two representations, so choose10. Since1 can begin a representation of10, take it; then3 can follow, and finally6, giving1 3 6 rather than4 6.
Why it works
The knapsack invariant counts each subset exactly once by its largest processed index. The suffix table gives exact feasibility for each remaining choice. At the first position where two representations differ, the one including the smallest currently feasible value is lexicographically smaller. Positive values ensure a completed representation cannot be a proper prefix of another representation of the same sum.
Watch out. Exclude sum0 from the first two outputs. Use unsigned long long for intermediate subset counts: the output guarantee bounds every final nonempty count below5·10^18, and intermediate counts cannot exceed final counts. Choose the larger sum on equal counts. Distinct positive input values are essential to the stated reconstruction.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>values(n);
for(int&value:values){
cin>>value;
}
sort(values.begin(),values.end());
int total=accumulate(values.begin(),values.end(),0);
vector<unsigned long long>ways(total+1,0);
ways[0]=1;
for(int value:values){
for(int sum=total;sum>=value;sum--){
ways[sum]+=ways[sum-value];
}
}
int distinct=0;
int chosen=0;
for(int sum=1;sum<=total;sum++){
if(ways[sum]>0){
distinct++;
if(ways[sum]>=ways[chosen]){
chosen=sum;
}
}
}
vector<vector<unsigned char>>can(n+1,vector<unsigned char>(total+1,0));
can[n][0]=1;
for(int i=n-1;i>=0;i--){
for(int sum=0;sum<=total;sum++){
can[i][sum]=can[i+1][sum];
if(sum>=values[i]&&can[i+1][sum-values[i]]){
can[i][sum]=1;
}
}
}
cout<<distinct<<'\n'<<chosen<<' '<<ways[chosen]<<'\n';
int remaining=chosen;
bool first=true;
for(int i=0;i<n&&remaining>0;i++){
// Take the smallest summand that still permits a completion.
if(remaining>=values[i]&&can[i+1][remaining-values[i]]){
if(!first){
cout<<' ';
}
cout<<values[i];
remaining-=values[i];
first=false;
}
}
cout<<'\n';
}