Divide 1 to n into two groups with minimum sum difference | CPP program to divide n integers in two groups such that absolute difference of their sum is minimum ; To print vector along size ; Print vector size ; Print vector elements ; To divide n in two groups such that absolute difference of their sum is minimum ; Find sum of all elements upto n ; Sum of elements of group1 ; If sum is greater then or equal to 0 include i in group 1 otherwise include in group2 ; Decrease sum of group1 ; Print both the groups ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printVector ( vector < int > v ) { cout << v . size ( ) << endl ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) cout << v [ i ] << " ▁ " ; cout << endl ; } void findTwoGroup ( int n ) { int sum = n * ( n + 1 ) / 2 ; int group1Sum = sum / 2 ; vector < int > group1 , group2 ; for ( int i = n ; i > 0 ; i -- ) { if ( group1Sum - i >= 0 ) { group1 . push_back ( i ) ; group1Sum -= i ; } else { group2 . push_back ( i ) ; } } printVector ( group1 ) ; printVector ( group2 ) ; } int main ( ) { int n = 5 ; findTwoGroup ( n ) ; return 0 ; }