Ca sa existe solutie , ai nevoie ca suma lor sa fie divizibila cu 2. n * (n + 1) / 2 se divide cu 2 inseamna ca n se divide cu 4 sau n + 1 se divide cu 4.
Daca n e divizibil cu 4 iei toate perechile i , n - i + 1 si le pui pe rand, alternativ, in multimea celor negative respectiv a celor pozitive.
1 2 3 4 5 6 7 8 : (1, 8 ) (3, 6) cu plus , celelalte cu minus.
Daca n + 1 e divizibil cu 4 faci aceeasi chestie pentru primele n - 1 numere, si pe al n-lea il pui in multimea cu suma mai mica.
1 2 3 4 5 6 7
Alternativ, poti face knapsack in O(n ^ 3).
Mersi mult, am gasit si un pattern pe pare si impare:
pare: + - pana la n/2 si apoi - + pana la n
impare: ++- si ramai cu o secventa para unde aplici patternul de la pare