How to solve the problem of placing arithmetic signs between numbers to get another number?

Question

Algorithms

Given N integers, the task is to place + and - signs between them to obtain the number S while preserving the original sequence of numbers in the expression, or to prove the impossibility of obtaining such S. For example, if the numbers are - [7, 3, 9] and S = 13, then the answer that satisfies the problem = 7-3+9=13
How can such an algorithm be implemented?

• 
  
• If the only solution is a brute-force search, then how to premutate to get all possible character arrangements?
  
• If there is a more efficient solution (smart search, or something tastier), then how to implement it?
  
• What would the algorithm look like without preserving the original sequence of numbers?
  

Answer 1

A full enumeration can be considered each character as a bit: 0 is a plus, 1 is a minus. It turns out that it is necessary to sort through all the numbers from 0to 2^(n-1)and their binary notation encodes signs.
For optimization, you can first check some extreme conditions:

• for example, "all pluses" should be >= S. To immediately cut off the check of options for obtaining 1E9 from only 1E6 units. The same check makes sense in the process of enumeration, to assess whether the remaining digits reach the sum remaining up to S
  
• Check parity - do not get odd from an even number of odd ones.
  
• Think about what to do with the same numbers, somehow cut off their mirror combinations.
  
• More to think
  

Answer 2

If you have only two characters and they can only be placed between numbers, then simply generate all numbers from 0 to 2 ^N-1 and take, for example, bit 0 for a minus, and bit 1 for a plus.