Question

Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S. В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= Xi <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000. Если получить требуемый результат невозможно, вывести "No solution", если можно, то вывести равенство. Если решение не единственное, вывести любое. Пример входные данные: 3 13 7 3 9 выходные данные: 7-3+9=13 Ограничение по времени: 1 сек, Ограничение по памяти: 64 мегабайта, Язык программирования: PascalABC.NET.

Answer 1

Ниже запрограммировано примерно следующее: делим массив на 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.