Forse la sparo grossa, magari però puo' essere un idea.

Hai il tuo array, potresti quindi ordinarlo (utilizzando ad esempio <i>sort()</i> di Arrays) e poi posizionarti a metà di esso. Inizierai quindi a scorrerlo da un lato e dall'altro. La semplificazione in questo caso è data dal fatto che il numero x è dato dalla somma di un numero che è in una metà con un altro che è nell'altra. Un altro vantaggio è interrompere il ciclo quando vai oltre alla somma. Nel tuo caso se hai {1,3,4,5,7,9} la metà è a lunghezza/2-1 (valore 4).
Ti conviene secondo me iniziare con un indice su 0 e l'altro su (lunghezza-1), in quanto ti permette di uscire da uno dei cicli. In pratica fai già 1+9=10, quindi decremento il secondo indice puntato sul 7. Ricomincio quindi a contarli facendo 7+1=8 e proseguo così...

Questo è per darti un idea.