Find four elements that sum to a given value | Set 2 | C ++ program to find 4 elements with given sum ; The following structure is needed to store pair sums in aux [ ] ; index ( int A [ ] ) of first element in pair ; index of second element in pair ; sum of the pair ; Following function is needed for library function qsort ( ) ; Function to check if two given pairs have any common element or not ; The function finds four elements with given sum X ; Create an auxiliary array to store all pair sums ; Generate all possible pairs from A [ ] and store sums of all possible pairs in aux [ ] ; Sort the aux [ ] array using library function for sorting ; Now start two index variables from two corners of array and move them toward each other . ; Driver code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; class pairSum { public : int first ; int sec ; int sum ; } ; int compare ( const void * a , const void * b ) { return ( ( * ( pairSum * ) a ) . sum - ( * ( pairSum * ) b ) . sum ) ; } bool noCommon ( pairSum a , pairSum b ) { if ( a . first == b . first a . first == b . sec a . sec == b . first a . sec == b . sec ) return false ; return true ; } void findFourElements ( int arr [ ] , int n , int X ) { int i , j ; int size = ( n * ( n - 1 ) ) / 2 ; pairSum aux [ size ] ; int k = 0 ; for ( i = 0 ; i < n - 1 ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { aux [ k ] . sum = arr [ i ] + arr [ j ] ; aux [ k ] . first = i ; aux [ k ] . sec = j ; k ++ ; } } qsort ( aux , size , sizeof ( aux [ 0 ] ) , compare ) ; i = 0 ; j = size - 1 ; while ( i < size && j >= 0 ) { if ( ( aux [ i ] . sum + aux [ j ] . sum == X ) && noCommon ( aux [ i ] , aux [ j ] ) ) { cout << arr [ aux [ i ] . first ] << " , ▁ " << arr [ aux [ i ] . sec ] << " , ▁ " << arr [ aux [ j ] . first ] << " , ▁ " << arr [ aux [ j ] . sec ] << endl ; return ; } else if ( aux [ i ] . sum + aux [ j ] . sum < X ) i ++ ; else j -- ; } } int main ( ) { int arr [ ] = { 10 , 20 , 30 , 40 , 1 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int X = 91 ; findFourElements ( arr , n , X ) ; return 0 ; }