CareerCup

Use a hash map.
Suppose array is arr = {2,8,3,6,4,7,9}
Now use a hash map
key = arr[i]
value = sum - arr[i]

if(value>0){
   map.put(key,value);
   if(map.containsKey(value))
      print key and value that add to the sum
}

The idea here is that suppose we want sum 5
now map will be
2,3
No entry for 8 as value >0
3,2 -> Here the value i.e. 2 exists as key -> 2,3 hence we have the sum 5

Try with Hash table.
Put all the array elements in Hash table.
Search for first array element in hash table and then x-a[0] value in hash table.
If it exists, return true.
else do this for other array elements present in hash table.

Complexity - O(n)

It can be implemented w/o any additional DS's in O(n Log n) time and with O(1) storage.
The below code and the driver app will find all the valid pairs, also included are the inlined comments:

#include <stdio.h>
#include <algorithm>
/*
Given an array of integers in the range INT_MIN to INT_MAX,
find all the pairs of elements that sum up to the given number @sum
Algorithm:
- Sort the input array
- Keep summing up the elements at the lowest and the highest current indices
- If the sum is > than the result, decrement the upper index
- If the sum is < than the result, increment the lower index
- If the sum = result, then
- found a valid pair; print the numbers
- converge the lower and upper indices (++lower, --upper)
- Loop until both indices meet
The above algorithm will find all the valid pairs, including positive,
negative and 0.
*/
bool find_sum(int arr[], int cnt, int sum)
{
int l, u, k;
bool bret = false;

/* Sort the input array */
std::sort(&arr[0], &arr[cnt]);
u = cnt - 1;
l = 0;

while (l < u) {
k = arr[l] + arr[u];
if (k == sum) { // found the two elements
printf("SUM: %-3d ELEMENTS (%d %d): %d %d\n",
sum, l, u,
arr[l], arr[u]);
bret = true;
l++;
u--;
}
else if (k < sum)
++l;
else
--u;
}
return bret;
}
int main(int argc, char* argv[])
{
int arr[] = {7, -4, 1, 0, -2, 3, 8, -9, 10, 1, 0, 20, 2};
int cnt = sizeof(arr)/sizeof(arr[0]);

for (int i = -10; i < 20; i++)
find_sum(arr, cnt, i);
return 0;

}
}}}

public boolean sumExists ( int [ ] array, int sum ) {

	if ( array == null )
		return false;

	HashSet<Integer> hs = new HashSet<Integer> ( );

	for ( int i=0; i<array.length; i++) {
		if ( hs.contains(sum-array[i] )
			return true;
		hs.add(array[i]);
	}
	
	return false;
}

Hash the array.

Iterate the array and check if x-a[i] exists in the hash.
Corner case is if x=4 and a[i]=2 and no other two is there in the array.

@ Gamodg try with input {1,3,5,7,9}
sum=10.

Create empty set. Iterate from left to right in the array. At each arr[i] item check whether X-arr[i] is already in the set. If yes, return true, else put arr[i] into the set and continue.

Linear time and space, no need to handle special case.