Как решить задачу расстановки арифметических знаков между числами для получения другого числа?
================================================================================================

 Даны N целых чисел, задача - расставить между ними знаки + и - для получения числа S с сохранением исходной последовательности чисел в выражении, или доказательства невозможности получения такого S. Например, если числа - [7, 3, 9] и S = 13, то ответ, удовлетворяющий задаче = 7-3+9=13  
  

 Как можно реализовать такой алгоритм?  
* 
* Если единственное решение - тупой перебор, то как сделать премутацию для получения всех возможных вариантов расстановки знаков?
* Если есть более эффективное решение (умный перебор, или что то вкуснее), то как его реализовать?
* Как выглядел бы алгоритм без сохранения исходной последовательности чисел?

 

 Полным перебором можно считать каждый знак битом: 0 это плюс, 1 минус. Получается, надо перебрать все числа от `0` до `2^(n-1)` и их двоичная запись кодирует знаки.  
  

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

 

 Если у вас только два знака и ставиться они могут только между числами, то просто генерируете все числа от 0 до 2N-1 и принимаете, например, бит 0 за минус, а бит 1 за плюс.