Qeyd edək ki, əgər $n$ və n - 3 ədədlərini bir qrupa, n - 1 və n - 2 ədədlərini isə digər qrupa yerləşdirsək (hər qrupdakı ədədlərin cəmi eyni olacaq), məsələ kiçik ölçülü analoji məsələyə, yəni 1, 2, ..., n - 4 ədədlərinin qruplara bölünməsinə gətirilir.

n \le 3 üçün ədədləri qruplara aşağıdakı kimi paylayırıq:

• Əgər üç ədəd $1,2,3$ qalırsa, onları iki qrupa bölmək olar: $\{1,2\}$ və $\{3\}$.

• Əgər iki ədəd $1,2$ qalırsa, onları qruplara bölürük: $\{1\}$ və $\{2\}$. Qruplardakı ədədlərin cəmlərinin fərqi $1$ olacaq.

• Əgər bir ədəd $1$ qalırsa, onu istənilən qrupa yerləşdirmək olar. Qruplardakı ədədlərin cəmlərinin fərqi $1$ olacaq.

Əgər $1$-dən $n$-ə qədər bütün ədədlərin cəmi cütdürsə, onları cəmi bərabər olan iki qrupa bölmək olar.

Əgər $1$-dən $n$-ə qədər bütün ədədlərin cəmi təkdirsə, onları cəmlərinin fərqi $1$-ə bərabər olan iki qrupa bölmək olar.

Misal

Tutaq ki, n = 10. Ədədləri qruplara aşağıdakı kimi yerləşdiririk:

Tutaq ki, n = 11. Ədədləri qruplara aşağıdakı kimi yerləşdiririk:

Alqoritmin reallaşdırılması

$n$ giriş qiymətini oxuyuruq.

scanf("%d", \&n);

Qruplardakı ədədlərin başlanğıc cəmləri s_1 və s_2-ni $0$-a bərabər təyin edirik.

s1 = s2 = 0;

$n$-dən $1$-ə qədər azalan ardıcıllıqla ədədləri gözdən keçiririk.

for (i = n; i \> 0; i--)

Əgər s_1 \< s_2 olarsa, $i$ ədədini birinci qrupa daxil edirik. Əks halda $i$ ədədini ikinci qrupa daxil edirik.

  if (s1 \< s2)
  {
    s1 += i;
    a.push_back(i);
  }
  else
  {
    s2 += i;
    b.push_back(i);
  }

Qrupların ölçülərini çıxarırıq.

printf("%d %d\n", a.size(), b.size());

Birinci qrupun ədədlərini çıxarırıq.

for (i = 0; i \< a.size(); i++)
  printf("%d ", a[i]);
printf("\n");

İkinci qrupun ədədlərini çıxarırıq.

for (i = 0; i \< b.size(); i++)
  printf("%d ", b[i]);
printf("\n");