1214. How Many Ways to Reach the Target With Plus and Minus

A string of digits is given, and a target. Between each pair of neighbouring digits you may put a +, put a -, or put nothing at all, which joins the two digits into one longer number. Report how many of the resulting expressions evaluate to the target.

An operand of two or more digits may not begin with 0. A single 0 is fine. The expression is evaluated left to right, and since the only operators are + and - there is no precedence to worry about.

123 with target 6 -> 1 only 1+2+3 105 with target 5 -> 1 only 10-5; 1+05 is illegal 000 with target 0 -> 4 the four sign choices on 0+0+0

## What most people try first

Build every operator string, all 3^(n-1) of them, paste it together, and evaluate the result by parsing the text. That works and it is doing the work twice: the operands are taken apart into digits, reassembled into text, and then parsed back into numbers. A recursion that chooses the next operand directly never converts anything back.

## The method

Walk the string choosing the next operand, carrying the running value and the sign the next operand will take:

go(acc, sign, start): for end in start+1 .. n: p = s[start .. end-1] if p has a leading zero and is longer than one digit: break v = value of p if end == n: if acc + sign * v == target: count += 1 else: go(acc + sign * v, +1, end) go(acc + sign * v, -1, end)

The leading-zero test is a break and not a continue. Once the operand starting at start has a leading zero, every longer operand from the same position has the same leading zero, so the loop is finished rather than skipping one length.

## Overflow, which is the real content of this problem

The operands can be big. Ten digits with no operators at all is a single operand of up to 9999999999, which is about 10^10 and far above INT_MAX = 2147483647. So the operand values and the running total must be held in a 64-bit integer. In C and C++ that is long long, in Java long. In JavaScript a plain number is an exact integer below 2^53, about 9 * 10^15, and 10^10 is well inside that, so ordinary arithmetic is exact there and BigInt is not needed; a bitwise operator anywhere would truncate to 32 bits and ruin it.

The target itself is bounded to fit in a signed 32-bit integer. Note that 2 * 10^9 FITS, since INT_MAX is 2147483647, so the bound here is not the false claim it is often written as.

Now the part worth knowing, because it is counter-intuitive. A 32-bit accumulator is NOT wrong in the way you would expect. Addition and subtraction modulo 2^32 behave exactly like addition and subtraction, so if the true value of an expression fits in 32 bits, a 32-bit computation of it is correct no matter how large the intermediate sums got. Wrapping cancels itself out.

What a 32-bit build actually gets wrong is the PARSED OPERAND. 4294967296 is 2^32, so parsing it into a 32-bit integer gives 0, and the one-operand expression then matches a target of 0 when it should not: the true answer for that input is 26 and a 32-bit build answers 27. Likewise 9999999999 wraps to 1410065407, a value no genuine expression over those digits can produce, so a target of 1410065407 has a true answer of 0 and a 32-bit build answers 1. Both of those are tests.

## The settled boundaries

A one-digit string has exactly one expression, the digit itself, so the answer is 1 when the target is that digit and 0 otherwise; both are tested. A string of zeros admits only single-digit operands, since any longer one has a leading zero, so the count is the number of sign choices, 2^(n-1), when the target is 0.

## Cost

Three choices per gap gives O(3^(n-1)) leaves at worst, which at n = 10 is 19683, and the leading-zero break cuts that sharply on strings containing zeros. O(n) per operand to compute its value.

Constraints - `1 ≤ length of the string ≤ 10` - `-2 * 10^9 ≤ target ≤ 2 * 10^9`, which fits in a signed 32-bit integer - an operand can reach `9999999999`, which does not, so operand values and the running total need 64 bits - the answer is at most `3^9 = 19683`