Generowanie zbiorów 2-elementowych o określonej sumie

Witam
Mam problem z zadaniem podanym w załączniku.
Rozwiązanie powinno być złożoności liniowej O(n).
Oto mój kod dla rozwiązania O(n^2)

 
#include<iostream>
#include<fstream>
////////////////////////////Zlozonosc n(n-1) = O(n^2)

using namespace std;


int main()
{
	fstream file,file2;
	file.open("In0102.txt",ios::in); if(!file.good()) {cout<<"Error"; return 1;}
	file2.open("Out0102.txt",ios::out);
	
	int n,k;
	file>>n>>k;
	int *table = new int[n];
	bool *table2 = new bool[n];
	for(int i=0; i<n; ++i) table2[i] = 0; 
	
	//wczytanie n liczb z pliku
	for(int i=0; i<n; ++i)
	{
		file>>table[i];
	}

	
	int min_set = 0; file2<<"0"<<endl;
	for(int i=0; i<n; ++i )
	{
		if(table2[i]==1) continue;
		
		int sum = -1;
		int v = -1;
		
		for(int j=i+1; j<n; ++j)
		{
			if(table2[j]==1) continue;
			
			if((sum < (table[i]+table[j])) && ((table[i]+table[j]) <= k))
				{
					sum = table[i]+table[j];
					v = j;	
					
				}	
		}
		
		if(v!=-1) 
		{
			table2[i] = 1;
			table2[v] = 1;
			file2<<table[i]<<" "<<table[v]<<endl;
		}
		else 
		{
			table2[i] = 1;
			file2<<table[i]<<endl;
		}
		++min_set;
		
	}
	 file2.seekp(0);
	 file2<<min_set<<endl;
	delete [] table2;
	delete [] table;
	
	return 0;
}

Może ktoś podsunie jakiś sprytny sposób na rozwiązanie tego liniowo? Ja już nie mam pomysłów.

Posortować przez zliczanie - O(n)

Brać największą liczbę (idąc z prawej), brać najmniejszą (idąc z lewej). Da się utworzyć parę? Tak->Utwórz. Nie->Utwórz zbiór 1-elementowy z tej największej.

Brać kolejną największą, brać najmniejszą. Da się utworzyć parę? ....

1 1 4 5 5 6 8 12    # k = 8
              12    # {12}
            8       # {12} {8}
1         6         # {12} {8} {1,6}
  1     5           # {12} {8} {1,6} {1,5}
      5             # {12} {8} {1,6} {1,5} {5}
    4               # {12} {8} {1,6} {1,5} {4} {5}

Ja bym wykorzystał tu "zliczanie". Masz raptem 100 liczb o niskim zakresie (0-150) wiec zrób tablicę o 150 elementach, wpakuj tam dane wejściowe na zasadzie tablica[liczba]=true jeśli liczba wystąpiła na wejściu. To wykonujesz liniowo. Następnie samo szukanie par jest dość trywialne -> wybierasz sobie pierwszą liczbę i dobierasz do niej największą która da sumę <=k czyli dla liczby x sprawdzasz czy w tablicy pod indeksem k-x masz liczbę (czyli true). Jeśli masz to ją bierzesz i masz parę, a oba indeksy w tablicy oznaczasz na false. Jeśli liczby nie ma to to szukasz mniejszej. Jeśli x jest od razu za duże to wrzucasz je do osobnego zbioru.
To by nadal mogło dać rozwiązanie kwadratowe dla przypadku kiedy za każdym razem lecisz od samego końca tablicy do początku, dlatego warto zapamiętać sobie indeks do którego doszliśmy "w dół" szukając pary i nowe poszukiwania zaczynać od tego indeksu (za każdym razem szukamy liczby mniejszej, bo nasza pierwsza liczba jest większa).

Dzieki za pomysł na pewno przetestuje : )