fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, arr[100], tot, dp[100][100000], mark[100];
  6. int solve(int idx, int sum1){
  7.     if(idx == n){
  8.         int sum2 = tot - sum1;
  9.         //cout << sum1 << " " << sum2 << endl;
  10.         if(sum1 == sum2) return 1;return 0;
  11.     }
  12.     if(dp[idx][sum1] != -1) return dp[idx][sum1];
  13.     int v1 = 0, v2 = 0;
  14.     v1 = solve(idx+1, sum1);
  15.     v2 = solve(idx+1, sum1 + arr[idx]);
  16.     if(v1 + v2 > 0) dp[idx][sum1] = 1;
  17.     else dp[idx][sum1] = 0;
  18.     return dp[idx][sum1];
  19. }
  20.  
  21. void check(int idx, int sum1){
  22.     if(idx == n) return;
  23.     int v1 = solve(idx+1, sum1);
  24.     int v2 = solve(idx+1, sum1 + arr[idx]);
  25.     if(v1 == 1){
  26.         mark[idx] = 1;
  27.         check(idx+1, sum1);
  28.     }else{
  29.         mark[idx] = 2;
  30.         check(idx+1, sum1 + arr[idx]);
  31.     }
  32. }
  33.  
  34. int main(){
  35.     cin >> n;
  36.     for(int i = 0;i < n;i++) cin >> arr[i], tot += arr[i];
  37.     memset(dp, -1, sizeof dp);
  38.     int ct = solve(0, 0);
  39.     if(ct == 0){
  40.         cout << "No Partition" << endl;
  41.     }else{
  42.         check(0, 0);
  43.         for(int i = 0;i < n;i++) if(mark[i] == 1) cout << arr[i] << " ";cout << endl;
  44.         for(int i = 0;i < n;i++) if(mark[i] == 2) cout << arr[i] << " ";cout << endl;
  45.     }
  46. }
  47.  
Success #stdin #stdout 0.04s 42480KB
comments (?)
stdin 
4
1 3 5 7
stdout 
1 7 
3 5
https://ideone.com/6MKLK0
language:
C++14 (gcc 8.3)
created:
9 years 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!