Place arithmetic signs in correct order to get the number

Question

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(2ⁿ)
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?

Answer 1

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 > 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(2ⁿ) 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 2ⁿ 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.

Answer 2

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;
}