https://leetcode.com/problems/additive-number/

If we have first number and second one, the rest of numbers are determined.

So we just select first and second number as many as possible and examine if the rest of the number is
the ones we want. Noted that the total length of the first and second number should be no more than the
rest of the numbers because addition only increase the length of the number. To prevent overflow from
large integer, we can use BigInteger since it supports arbitrary-precision integers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.math.BigInteger;
public class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        for (int i = 1; i <= n / 2; i++) {
            // i stops before midpoint because the length of result that i plus something >= 0 need
            // to be >= i.
            if (num.charAt(0) == '0' && i > 1) {
                // number with leading 0 is not valid, but 0 alone is a valid number
                return false;
            }
            BigInteger i1 = new BigInteger(num.substring(0, i));
            for (int j = 1; Math.max(i, j) <= n - i - j; j++) {
                if (num.charAt(i) == '0' && j > 1) {
                    // 0 alone is valid number but number with leading 0 is not valid, check next
                    break;
                }
                BigInteger i2 = new BigInteger(num.substring(i, i + j));
                if (isValid(i1, i2, num, i + j)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean isValid(BigInteger i1, BigInteger i2, String num, int start) {
        if (start == num.length()) {
            return true;
        }
        i2 = i2.add(i1); // target number
        i1 = i2.subtract(i1);
        String target = i2.toString();
        if (num.startsWith(target, start)) {
            return isValid(i1, i2, num, start + target.length());
        } else {
            return false;
        }
    }
}