fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int n, k;
  9.     cin >> n >> k;
  10.     vector<int> c(n);
  11.     for(int i = 0; i < n; i++) 
  12.         cin >> c[i];
  13.  
  14.     static bool dp[501][501] = {};
  15.     static bool back[501][501] = {};
  16.     dp[0][0] = true;
  17.  
  18.     // 1) Standard subset-sum DP to know which prefixes can make which sums
  19.     for(int i = 0; i < n; i++){
  20.         for(int s = 0; s <= k; s++){
  21.             if(!dp[i][s]) continue;
  22.             dp[i+1][s] = true;
  23.             if(s + c[i] <= k) 
  24.                 dp[i+1][s + c[i]] = true;
  25.         }
  26.     }
  27.  
  28.     // 2) Backtrack from (n,k) to mark which (i, sum) lie on *some* path that reaches k
  29.     back[n][k] = true;
  30.     for(int i = n; i > 0; i--){
  31.         for(int s = 0; s <= k; s++){
  32.             if(!back[i][s]) continue;
  33.             // case 1: we didn’t use coin i–1
  34.             if(dp[i-1][s]) 
  35.                 back[i-1][s] = true;
  36.             // case 2: we did use coin i–1
  37.             if(s >= c[i-1] && dp[i-1][s - c[i-1]])
  38.                 back[i-1][s - c[i-1]] = true;
  39.         }
  40.     }
  41.  
  42.     // 3) Collect all sums s that appear in back[i][s] for any i
  43.     vector<int> ans;
  44.     vector<bool> seen(k+1,false);
  45.     for(int i = 0; i <= n; i++){
  46.         for(int s = 0; s <= k; s++){
  47.             if(back[i][s] && !seen[s]){
  48.                 seen[s] = true;
  49.                 ans.push_back(s);
  50.             }
  51.         }
  52.     }
  53.     sort(ans.begin(), ans.end());
  54.  
  55.     cout << ans.size() << "\n";
  56.     for(int x : ans) 
  57.         cout << x << " ";
  58.     cout << "\n";
  59.     return 0;
  60. }
  61.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 18
5 6 1 10 12 2
stdout
copy 
5
0 5 6 16 18
https://ideone.com/1qqJOo
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!