3
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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(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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.