fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. void findSubset(vector<int>& arr, vector<vector<int>>& count, int M) {
  9.     vector<int> result;
  10.     int n = arr.size();
  11.     int j = M;
  12.  
  13.     for (int i = n; i > 0 && j > 0; ) {
  14.         if (count[i][j] != count[i-1][j]) {
  15.             result.push_back(arr[i-1]);
  16.             j -= arr[i-1];
  17.             i--;
  18.         } else {
  19.             i--;
  20.         }
  21.     }
  22.  
  23.     cout << M << "=";
  24.     for (int k = 0; k < result.size(); ++k) {
  25.         if (k != 0) {
  26.             cout << "+";
  27.         }
  28.         cout << result[k];
  29.     }
  30.     cout << endl;
  31. }
  32.  
  33. bool subsetSum(vector<int>& arr, int M) {
  34.     int n = arr.size();
  35.     vector<vector<int>> count(n + 1, vector<int>(M + 1, INT_MAX));
  36.     vector<vector<bool>> dp(n + 1, vector<bool>(M + 1, false));
  37.  
  38.     for (int i = 0; i <= n; ++i) {
  39.         dp[i][0] = true;
  40.         count[i][0] = 0;
  41.     }
  42.  
  43.     for (int i = 1; i <= n; ++i) {
  44.         for (int j = 1; j <= M; ++j) {
  45.             dp[i][j] = dp[i - 1][j];
  46.             count[i][j] = count[i - 1][j];
  47.             if (arr[i - 1] <= j) {
  48.                 if (dp[i - 1][j - arr[i - 1]] && count[i - 1][j - arr[i - 1]] + 1 < count[i][j]) {
  49.                     dp[i][j] = true;
  50.                     count[i][j] = count[i - 1][j - arr[i - 1]] + 1;
  51.                 }
  52.             }
  53.         }
  54.     }
  55.  
  56.     if (dp[n][M]) {
  57.         findSubset(arr, count, M);
  58.     } else {
  59.         cout << "No\n";
  60.     }
  61.  
  62.     return dp[n][M];
  63. }
  64.  
  65. int main() {
  66.     int N, M;
  67.  
  68.     cin >> N;
  69.     vector<int> arr(N);
  70.  
  71.     for (int i = 0; i < N; ++i) {
  72.         cin >> arr[i];
  73.     }
  74.  
  75.     cin >> M;
  76.  
  77.     subsetSum(arr, M);
  78.  
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
8
1 1 3 4 5 10 20 50
27
stdout
copy 
27=20+4+3
https://ideone.com/SCyLsq
language:
C++14 (gcc 8.3)
created:
42 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!