fork(15) download
copy 
  1. // Author :: Gaurav Ahirwar
  2. #include<bits/stdc++.h>
  3. #define FOR(i,n) for(int i=(0);i<(n);i++)
  4. #define INF INT_MAX
  5. using namespace std;
  6.  
  7. void getdiff(int arr[], int seta[], int setb[], int fseta[], int fsetb[], int inda, int indb, int i, int suma, int sumb, int &diff) {
  8.  
  9. 	if(i < 0 && abs(suma - sumb) < diff) {
  10. 		FOR(j,inda) fseta[j] = seta[j];
  11. 		FOR(j,indb) fsetb[j] = setb[j];
  12. 		fseta[inda] = -1;
  13. 		fsetb[indb] = -1;
  14.  		diff = abs(suma-sumb);
  15. 	}
  16.  
  17. //	static int x = 0; cout << "Iteration = " << ++x << " \n";
  18. 	if(i < 0) return;
  19.  
  20. 	seta[inda] = arr[i];
  21. 	getdiff(arr, seta, setb, fseta, fsetb, inda+1,indb, i-1, suma + arr[i], sumb, diff);
  22. 	setb[indb] = arr[i];
  23. 	getdiff(arr, seta, setb, fseta, fsetb, inda,indb+1, i-1, suma , sumb + arr[i], diff);
  24. }
  25.  
  26. void topdown(int arr[], int n) {
  27.  
  28. 	int seta [n+1], setb [n+1], fseta [n+1], fsetb [n+1];
  29. 	FOR(i,n) seta[i] = -1, setb[i] = -1;
  30. 	int suma = 0, sumb = 0, indexa = 0, indexb = 0;
  31. 	int diff = INF, array_index = n-1;
  32.  
  33. 	getdiff(arr, seta, setb, fseta, fsetb, indexa, indexb, array_index, suma, sumb, diff);
  34.  
  35. 	cout << "Set 1 => ";
  36. 	for(int i = 0; i <= n && fseta[i] != -1; i++) cout << fseta[i] << " ";
  37. 	cout << endl << "Set 2 => ";
  38. 	for(int i = 0; i <= n && fsetb[i] != -1; i++) cout << fsetb[i] << " ";	
  39. 	cout << "\nDifference => " << diff << endl;
  40. }
  41.  
  42. int main() {
  43.  
  44. 	int arr[] = {1,7,4,11}; 
  45. 	int n = sizeof(arr)/sizeof(arr[0]);
  46. 	topdown(arr, n);
  47. 	return 0;
  48. }
Success #stdin #stdout 0s 3140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Set 1 => 11 1 
Set 2 => 4 7 
Difference => 1
https://ideone.com/g9HvtO
language:
C++14 (gcc 8.3)
created:
8 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!