Как решить задачу расстановки арифметических знаков между числами для получения другого числа?
Полным перебором можно считать каждый знак битом: 0 это плюс, 1 минус. Получается, надо перебрать все числа от 0 до 2^(n-1) и их двоичная запись кодирует знаки.
Для оптимизации можно сначала проверить некоотрые крайние условия:например, «все плюсы» должны быть >= S. Чтобы сразу отсечь проверку вариантов получения 1E9 из всего 1E6 единиц. Эта же проверка имеет смысл в процессе перебора, для оценки, дотянутся ли оставшиеся цифры до оставшейся до S суммыПроверить четность - из четного числа нечетных не получить нечетное. Подумать, что делать с одинаковыми числами, как-то отсечь их зеркальные комбинации.Ещё подумать
Если у вас только два знака и ставиться они могут только между числами, то просто генерируете все числа от 0 до 2N-1 и принимаете, например, бит 0 за минус, а бит 1 за плюс.