306.md

public class Solution {

    public static void main(String[] args) {
        String num = "11235813213455890144";
        System.out.println(new Solution().isAdditiveNumber(num));
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) {
            return false;
        }

        List<BigInteger> path = new ArrayList<>(num.length());

        return backtrack(num, path, 0);

    }

    private boolean backtrack(String num, List<BigInteger> path, int idx) {
        if (idx == num.length()) {
            return path.size() >= 3;
        }

        int diff = num.length() - idx;
        boolean result = false;
        for (int i = 1; i <= diff; i++) {
            String sub = num.substring(idx, idx + i);
            if (sub.length() > 1 && sub.startsWith("0")) {
                return false;
            }
            BigInteger tmp = new BigInteger(sub);
            if (path.size() < 2) {
                path.add(tmp);
            } else {
                BigInteger sum = path.get(path.size() - 1).add(path.get(path.size() - 2));
                if (tmp.equals(sum)) {
                    path.add(tmp);
                } else if (tmp.compareTo(sum) < 0) {
                    continue;
                } else {
                    return false;
                }
            }
            result = backtrack(num, path, idx + i);
            if (result) {
                return true;
            }

            path.remove(path.size() - 1);
        }
        return false;
    }
}

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().isAdditiveNumber("199100199"));
    }

    public boolean isAdditiveNumber(String num) {
        if (num.length() < 3) {
            return false;
        }

        return dfs(0, 0L, 0L, 0, num);
    }

    private boolean dfs(int index, long sum, long pre, int count, String nums) {
        if (index == nums.length()) {
            return count >= 3;
        }

        long value = 0L;
        for (int i = index; i < nums.length(); i++) {
            if (i > index && nums.charAt(index) == '0') {
                return false;
            }

            value = value * 10 + (nums.charAt(i) - '0');

            if (count >= 2) {
                if (value < sum) {
                    continue;
                } else if (value > sum) {
                    return false;
                }
            }

            boolean res = dfs(i + 1, pre + value, value, count + 1, nums);
            if (res) {
                return true;
            }
        }
        return false;
    }
}