Дано множество чисел $$$A = \{a_1, a_2, \dots, a_n\}$$$. Требуется построить правильную скобочную последовательность, в которой мультимножество расстояний между парными скобками будет равно $$$A$$$.
Несложно заметить, что расстояние между парными скобками всегда четно, поэтому если в $$$A$$$ есть нечетное число, решения точно не существует.
Рассмотрим самое большое число из $$$A$$$. Пара скобок, соответствующая этому расстоянию, не может быть вложена ни в какую другую пару скобок. Поэтому, можно поставить такую пару скобок в самом начале скобочной поледовательности.
Таким образом, задачу можно решить методом динамического программирования по подмножествам. Состоянием является мультимножество чисел, являющееся подмножеством $$$A$$$. Для каждого мультимножества нас интересует, существует ли ПСП, соответствующая такому мультимножеству. И если искомая ПСП существует, сохраним любую подходящую. Пустому мультимножеству соответствует пустая ПСП. Для любого другого множества, выберем самое большое число из множества. Пусть оно равно $$$x$$$. Поставим первую пару скобок на расстоянии $$$x$$$. Тогда оставшиеся числа из множества нужно разбить на две части: одно будет содержать $$$\frac{x}{2}$$$ чисел, и будет соответствовать ПСП внутри первой пары скобок, и вторая часть будет содержать все оставшиеся числа и будет соответствовать ПСП правее первой пары скобок. Значит, нужно перебрать способы выбрать $$$\frac{x}{2}$$$ чисел из текущего множества.
Для оценки асимптотики, просуммируем по всем множествам $$$C_{k - 1}^{\lfloor (k - 1) / 2 \rfloor}$$$, где $$$k$$$ — количество чисел в множестве. Получается порядка $$$4 \cdot 10^8$$$. На практике, такое решение уже укладывается в ограничение по времени. Можно еще ускорить решение, если заметить, что различных состояний может быть меньше, чем $$$2^n$$$, потому что в $$$A$$$ могут встречаться повторяющиеся числа.