fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int MOD = 1000000007;
  5. const int MX = 1000001;
  6.  
  7. ll modExp(ll base, ll power) {
  8.     if (power == 0) return 1;
  9.     ll cur = modExp(base, power / 2);
  10.     cur = (cur * cur) % MOD;
  11.     if (power % 2) cur = (cur * base) % MOD;
  12.     return cur;
  13. }
  14. ll inv(ll x) { return modExp(x, MOD - 2); }
  15. ll mul(ll A, ll B) { return (A * B) % MOD; }
  16. ll add(ll A, ll B) { return (A + B) % MOD; }
  17. ll sub(ll A, ll B) { return (A - B + MOD) % MOD; }
  18.  
  19. int main() {
  20.     ios::sync_with_stdio(false);
  21.     cin.tie(nullptr);
  22.  
  23.     int n, k;
  24.     cin >> n >> k;
  25.     vector<int> arr(n);
  26.     for (int i = 0; i < n; i++) cin >> arr[i];
  27.  
  28.     static bool dp[501][501] = {};
  29.     static bool backtrack[501][501] = {};
  30.     dp[0][0] = true;
  31.  
  32.     // forward DP: which sums j are reachable using first i elements
  33.     for (int i = 0; i < n; i++) {
  34.         for (int j = 0; j <= k; j++) {
  35.             if (!dp[i][j]) continue;
  36.             dp[i+1][j] = true;
  37.             if (j + arr[i] <= k)
  38.                 dp[i+1][j + arr[i]] = true;
  39.         }
  40.     }
  41.  
  42.     if (!dp[n][k]) {
  43.         cout << 0 << "\n";
  44.         return 0;
  45.     }
  46.  
  47.     // mark (n,k) as reachable in the backtrack table
  48.     backtrack[n][k] = true;
  49.     for (int i = n; i > 0; i--) {
  50.         for (int j = 0; j <= k; j++) {
  51.             if (!backtrack[i][j]) continue;
  52.             // you can either skip arr[i-1]
  53.             backtrack[i-1][j] = true;
  54.             // or have taken arr[i-1]
  55.             if (j >= arr[i-1]) {
  56.                 backtrack[i-1][j - arr[i-1]] = true;
  57.             }
  58.         }
  59.     }
  60.  
  61.     // collect all j such that at any prefix i, sum j is on a valid path to (n,k)
  62.     set<ll> res;
  63.     for (int i = 0; i <= n; i++)
  64.         for (int j = 0; j <= k; j++)
  65.             if (backtrack[i][j])
  66.                 res.insert(j);
  67.  
  68.     cout << res.size() << "\n";
  69.     for (ll x : res) 
  70.         cout << x << ' ';
  71.     cout << "\n";
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 18
5 6 1 10 12 2
stdout
copy 
18
0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18
https://ideone.com/7x16p8
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!