Ниже запрограммировано примерно следующее: делим массив на 2 части (в каждой будет не больше 12 элементов), для каждой части вычисляем всевозможные суммы с плюсами-минусами. Затем для каждой суммы из левой части пытаемся найти бинпоиском сумму из правой части, чтобы получилось то, что надо. Если нашли - повторяем всё для каждой части и пытаемся восстановить ответ.
function getAllSums(myarr: array of integer): array of integer;
begin
var answer := arrFill(round(power(2, myarr.Length)), 0);
for var i := 0 to round(power(2, myarr.Length)) - 1 do
begin
var s := 0;
var k := i;
for var j := 0 to myarr.Length - 1 do
begin
if k mod 2 = 0 then s += myarr[j] else s -= myarr[j];
k := k div 2;
end;
answer[i] := s;
end;
result := answer;
end;
function getSolution(myarr: array of integer; s: integer): array of boolean;
begin
if myarr.Length = 1 then
begin
result := Arr(myarr[0] = s);
exit;
end;
var sums_left := getAllSums(myarr[:myarr.Length div 2]);
var sums_right := getAllSums(myarr[myarr.Length div 2:]).Sorted.ToArray;
for var i := 0 to sums_left.Length - 1 do
if sums_right.BinarySearch(s - sums_left[i]) >= 0 then
begin
result := getSolution(myarr[:myarr.Length div 2], sums_left[i]) +
getSolution(myarr[myarr.Length div 2:], s - sums_left[i]);
exit;
end;
result := new boolean[0];
end;
begin
var n := readinteger;
var s := readinteger;
var xn := readarrinteger(n).Select(x->abs(x)).ToArray;
var signs := getSolution(xn, s);
if signs.Length = 0 then
print('No solution')
else
begin
if signs[0] then
write(xn[0])
else
write('-', xn[0]);
for var i := 1 to xn.Length - 1 do
if signs[i] then
write('+', xn[i])
else
write('-', xn[i]);
write('=', s);
end;
end.