Place arithmetic signs in correct order to get the number Given a list of numbers, place signs + or - in order to get the
  required number. 
  
  If it's possible then return true, otherwise return false 
  
  [1, 2, 3, 4, 5, 7]; 12 -> true, because 1 + 2 + 3 + 4 - 5 + 7 = 12
  
  [5, 3]; 7 -> false, because 5 + 3 != 7 and 5 - 3 != 7


I came up with the following brute force solution:

public static boolean trueOrNot(int number, List&lt;Integer&gt; numbers) {
        boolean found = false;
        int i = 0;
        while (!found &amp;&amp; i &lt; (1 &lt;&lt; numbers.size())) {
            int tmpResult = 0;
            for (int j = 0; j &lt; numbers.size(); j++) {
                int num = numbers.get(j);
                if ((i &amp; (1 &lt;&lt; j)) &gt; 0) {
                    num = -num;
                }
                tmpResult += num;
            }
            found = tmpResult == number;
            i++;
        }
        return found;
}


Basically, I took for consideration binary representations of numbers 0000, 0001, 0010...2^n and iterate over every bit, thus getting all possible combinations. 0 is a + sign and 1 is - sign. 
Then I calculate temporal result and once it is equal to the sought number I break out from loop.

Time complexity: O(2n)
Space complexity: O(1)

I just wondering is there any more effective solution with the help of Dynamic Programming, for example?

Feedback for the current solution?
There is one technique, of transforming a problem to a more comfortable one.
Here one could do it a couple of times:

First the original problem sum = term[0] ± term[1] ± ....

static boolean additive(int sum, int... terms) {
    if (terms.length == 0) {
        return sum == 0;
    }
    if (terms.length == 1) {
        return sum == terms[0];
    }
    int sum2 = sum - terms[0];
    int[] terms2 = IntStream.of(terms).skip(1).map(Math::abs).sorted().toArray();
    // Also an occasion to use Arrays.copyOfRange(terms, 1, terms.length);
    return additive2(sum2, terms2);
}


You can subtract the first term from the sum, and then have the possibly more regular problem sum == ∑i ±term[i]. All terms positive, and sorted.

/**
 * @param sum to be formed by the sum of every term * ± 1.
 * @param terms, all absolute, and sorted.
 */
static boolean additive2(int sum, int... terms) {
    int termsSum = IntStream.of(terms).sum();
    if (sum &gt; termsSum) {
        return false;
    }
    int tooMuch = termsSum - sum;
    // Split the terms in added and subtracted ones.
    // The sum of the subtracted ones * 2 == tooMuch.
    if (tooMuch % 2 != 0) {
        return false;
    }
    if (tooMuch == 0) { // All positive terms.
        return true;
    }
    // Find subtracted terms:
    int subtractedSum = tooMuch / 2;
    return findSubtracted(subtractedSum, terms.length - 1, terms);
}


Then math properties appear: the difference between the sum of absolute terms and the requested sum must be twice the sum of the negative/subtracted terms.
An odd difference means failure. Nice.

Now one only needs to recursively find the subtracted terms, starting with the largest terms. O(2n) but with some cuts: if the term is too large, in the recursion sum &lt; 0, and done: sum is decreased as fast as possible.

static boolean findSubtracted(int sum, int i, int[] terms) {
    if (sum &lt;= 0) {
        return sum == 0;
    }
    if (i &lt; 0) {
        return false;
    }
    return findSubtracted(sum - terms[i], i - 1, terms)
            || findSubtracted(sum, i - 1, terms);
}

public static void main(String[] args) throws XMLStreamException {
    System.out.println(additive(12, 1, 2, 3, 4, 5, 7)); // true, because 1 + 2 + 3 + 4 - 5 + 7 = 12
    System.out.println(additive(7, 5, 3)); // false, because neither 5 + 3 != 7 or 5 - 3 != 7
}


Take


Problem: 1 + 2 + 3 + 4 - 5 + 7 = 12
1 + 2 + 3 + 4 + 5 + 7 = 22; tooMuch = 10, subtractedSum = 5
-7? - false
-5? - true


This might not be the best solution, but it exposes some math intelligence.
For instance 1 + 2 + 3 + 4 - 5 + 7 = 13 will fail fast.

Dynamic programming, operations research and such are indeed worthwile in real life problems, especially if approximations / near solutions count too. Traffic optimisation and such.



A remark on iterating upto 2n with bit tests: nice and I did it myself on occasion. However here my code accomplishes the same with 2 recursive calls in the function. Which certainly is less effective, but more readable. Do this (micro-)optimisation last, as it hampers mental flexibility on the mathematical properties themselves. I think.