# 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<Integer> numbers) {
boolean found = false;
int i = 0;
while (!found && i < (1 << numbers.size())) {
int tmpResult = 0;
for (int j = 0; j < numbers.size(); j++) {
int num = numbers.get(j);
if ((i & (1 << j)) > 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);
}


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 > 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 < 0, and done: sum is decreased as fast as possible.

static boolean findSubtracted(int sum, int i, int[] terms) {
if (sum <= 0) {
return sum == 0;
}
if (i < 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.

Actually after some studying I figured out another optimal way of solving this problem:

public static boolean trueOrNot(int T, ArrayList<Integer> nums) {
Map<Integer, Map<Integer, Boolean>> cache = new HashMap<>();
return trueOrNot(nums, T, 0, 0, cache);
}

private static boolean trueOrNot(ArrayList<Integer> nums, int T, int i, int sum, Map<Integer, Map<Integer, Boolean>> cache) {
if (i == nums.size()) {
return sum == T;
}
if (!cache.containsKey(i)) cache.put(i, new HashMap<>());
Boolean cached = cache.get(i).get(sum);
if (cached != null) return cached;
boolean result =
trueOrNot(nums, T, i + 1, sum + nums.get(i), cache)
|| trueOrNot(nums, T, i + 1, sum - nums.get(i), cache);
cache.get(i).put(sum, result);
return result;
}