fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5. int n;
  6. cin>>n;
  7. int a[n];
  8. for(int i=0; i<n; i++){
  9. cin>>a[i];
  10. }
  11. int s;
  12. cin>>s;
  13. int dp[s+1]={0,};
  14. for(int i=0; i<n; i++){
  15. for(int j=a[i]; j<=s; j++){
  16. if(dp[j-a[i]]>0 or j==a[i]){
  17. if(dp[j]>dp[j-a[i]]+1 or dp[j]==0)
  18. dp[j]=dp[j-a[i]]+1;
  19.  
  20. }
  21. }
  22. }
  23. if(dp[s]==0){
  24. cout<<"No solution"<<endl;
  25. return 0;
  26. }
  27. while(dp[s]>0){
  28. for (int i=0; i<n; i++){
  29. if(s-a[i]>=0 and dp[s]==dp[s-a[i]]+1){
  30. cout<<a[i]<<" ";
  31. s-=a[i];
  32. break;
  33. }
  34. }
  35. }
  36. }
Success #stdin #stdout 0.01s 5304KB
stdin
5
1 3 7 12 32
40
stdout
1 7 32