Спершу зведемо задачу до x \ge 0: якщо x < 0, змінимо знак у і в усіх елементів — усі префіксні суми теж змінять знак, тому умова збережеться. Далі відсортуємо масив за зростанням.
Випадок x = \mathrm{sum}. Префікс довжини дорівнює сумі масиву за будь-якого порядку, тому відповідь — NO.
Випадок x = 0. Якщо \mathrm{sum} > 0, відсортуємо за спаданням: тоді середнє перших елементів не менше за загальне середнє, отже кожна префіксна сума додатна. Якщо \mathrm{sum} < 0 — за зростанням, і всі префіксні суми від'ємні. В обох випадках нуля серед них немає.
Випадок \mathrm{sum} < x. Підійде зростаючий порядок. У ньому прирости a_k не спадають, тому послідовність префіксних сум опукла, а отже свій максимум на вона досягає на кінці: це \max(a_1, \mathrm{sum}). Обидві величини менші за (якби a_1 \ge x > 0, то всі елементи були б не менші за і сума перевищила б ), тому недосяжне.
Далі вважаємо 0 < x < \mathrm{sum}; зокрема, додатні елементи точно є. Позначимо через найменший додатний елемент, а через — найбільший елемент масиву.
Випадок, коли додатні елементи не всі однакові (v \ne \mathit{mx}). Виведемо спочатку всі додатні за зростанням, потім усі недодатні. На додатній ділянці префіксні суми строго зростають; якщо якась із них дорівнює , це станеться рівно один раз, у деякій позиції . Виправимо це, помінявши елемент позиції з останнім додатним (а якщо їхні значення збігаються — перенесемо найменший додатний у кінець блоку). Обидві дії строго збільшують усі проміжні префіксні суми, тому позиція «перестрибує» через , а наступні суми й поготів більші. Зауважте, що остання сума додатного блоку не може дорівнювати : вона не менша за \mathrm{sum} > x, бо решта елементів недодатні.
Випадок, коли всі додатні дорівнюють . Позначимо їх кількість ; тоді сума додатних дорівнює pv \ge \mathrm{sum} > x.
Якщо v \nmid x, відсортуємо все за спаданням. Спочатку йдуть однакових елементів, тому префіксні суми — це v, 2v, \ldots, pv, і жодна з них не дорівнює . Далі суми лише спадають від до , а обидві ці межі більші за , тож і решта сум більші.
Якщо v \mid x, поставимо на перше місце будь-який недодатний елемент , який не ділиться на , потім усі додатні, потім решту. Тоді префіксні суми на зростаючій ділянці мають вигляд b + kv і не діляться на , отже не дорівнюють ; сама b \le 0 < x; а спадна ділянка знову лежить між і b + pv \ge \mathrm{sum}, тобто вище за .
Якщо ж усі недодатні теж діляться на , відповідь — NO. Справді, тоді всі елементи кратні ; поділивши все на , дістанемо задачу, де кожен додатний елемент дорівнює рівно . Послідовність префіксних сум іде від до \mathrm{sum}' > x' > 0, а вгору вона рухається лише кроками — отже, «перестрибнути» значення x' неможливо, і воно неодмінно буде досягнуте.
Складність — \mathcal{O}(n \log n) на тест через сортування.