Searching: Check if there exist 2 elements in an array whose sum is equal to the sum of rest of the array

Problem Statement:

Given an array, you need to 2 elements in the array, such that the sum of all the elements of the array is equal to 2 numbers.

Example:

Input  : arr[] = {2, 11, 5, 1, 4, 7}
Output : 4, 11

4 + 11 = 2 + 5 + 1 + 7

Solution 1: 

Find the sum of all array of the element. If the sum is odd, then return false.

Then divide sum by half.

Then find a pair with sum equal to the sum/2.

Once pair is found, print it and return.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;


bool solution_1 (int arr[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
		sum += arr[i];

	if (sum % 2 != 0)
		return false;

	sum = sum / 2;

	unordered_set<int> s;

	for (int i = 0; i < n; i++) 
	{
		int val = sum - arr[i];

		if (s.find(val) != s.end()) 
		{
			cout<< "Pair elements are "<< arr[i] << " and " << val;
			return true;
		}

		s.insert(arr[i]);
	}

	return false;
}

int main()
{
	int arr[] = { 2, 11, 5, 1, 4, 7 };
	int n = sizeof(arr) / sizeof(arr[0]);

	if (solution_1(arr, n) == false)
		printf("No pair found");
	
	return 0;
}

Output

Pair elements are 4 and 11