fork download
copy 
  1. /*
  2. Author : jayasurya
  3. */
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. // DP - Parition problem
  8. bool partition (int arr[], int n)
  9. {
  10.     int sum = 0;
  11.     int i, j;
  12.     for (i = 0; i < n; i++)
  13.       sum += arr[i];
  14.     if (sum%2 != 0)  
  15.        return false;
  16.     bool partSum[sum/2+1][n+1];
  17.  
  18.     for (i = 0; i <= n; i++)
  19.       partSum[0][i] = true;
  20.  
  21.     for (i = 1; i <= sum/2; i++)
  22.       partSum[i][0] = false;     
  23.  
  24.      for (i = 1; i <= sum/2; i++)  
  25.      {
  26.        for (j = 1; j <= n; j++)  
  27.        {
  28.          partSum[i][j] = partSum[i][j-1];
  29.          if (i >= arr[j-1])
  30.            partSum[i][j] = partSum[i][j] || partSum[i - arr[j-1]][j-1];
  31.        }        
  32.      }    
  33.      return partSum[sum/2][n];
  34. }     
  35.  
  36. int main()
  37. {
  38.   int n;
  39.   cin >> n;
  40.   int values[n];
  41.   for(int i=0; i<n; i++) cin >> values[i];
  42.   if (partition(values, n))
  43.      cout << "Gifts can be split between two friends";
  44.   else
  45.      cout << "Gifts cannot be split equally";
  46.   return 0;
  47. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
6
3
1
1
2
2
1
stdout
copy 
Gifts can be split between two friends
https://ideone.com/kXNakQ
language:
C++14 (gcc 8.3)
created:
7 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!