fork(1) 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. dp[a[i]]=1;
  16. for(int j=a[i]+1; j<=s; j++){
  17. if(dp[j-a[i]]>0 or j==a[i]){
  18. if(dp[j]>dp[j-a[i]]+1 or dp[j]==0)
  19. dp[j]=dp[j-a[i]]+1;
  20.  
  21. }
  22. }
  23. }
  24. if(dp[s]==0){
  25. cout<<"No solution"<<endl;
  26. return 0;
  27. }
  28. while(dp[s]>0){
  29. for (int i=0; i<n; i++){
  30. if(s-a[i]>=0 and dp[s]==dp[s-a[i]]+1){
  31. cout<<a[i]<<" ";
  32. s-=a[i];
  33. break;
  34. }
  35. }
  36. }
  37. }
Success #stdin #stdout 0s 5308KB
stdin
5
1 3 7 12 32
40
stdout
1 7 32