Question

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true 
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199

Thinking:

  • Method 1: 递归
    • 实际上只要确定了前两个operands以后所有的数字就被定下来了。
    • 我们通过循环获得所有输入的前两个数字的可能，通过递归判断是否可行。
    • 需要考虑以0开头的情况。
class Solution {
    public boolean isAdditiveNumber(String num) {
        if(num == null || num.length() == 0) return false;
        int len = num.length();
        for(int i = 1; i <= (len - 1)/2; i++){
            String num1Str = num.substring(0, i);
            if(i > 1 && num1Str.startsWith("0")) continue;
            Long num1 = new Long(num1Str);
            for(int j = i + 1; j < len; j++){
                String num2Str = num.substring(i, j);
                if(j - i > 1 && num2Str.startsWith("0")) continue;
                Long num2 = new Long(num2Str);
                if(isAdditiveNumber(num.substring(j), num1, num2)) return true;
            }
        }
        return false;
    }
    public boolean isAdditiveNumber(String remain, long op1, long op2){
        if(remain.length() == 0) return true;
        long sum = op1 + op2;
        String temp = sum + "";
        if(!remain.startsWith(temp))
            return false;
        else{
            return isAdditiveNumber(remain.substring(temp.length()), op2, sum);
        }
    }
}

Second time

class Solution {
    public boolean isAdditiveNumber(String num) {
        boolean result = false;
        for(int i = 1; i <= num.length() - 2; i++){
            for(int j = i + 1; j <= num.length() - 1; j++){
                if(i != 1 && num.substring(0, i).startsWith("0")) continue;
                if(j - i != 1 && num.substring(i, j).startsWith("0")) continue;
                result |= backtrace(num, Long.parseLong(num.substring(0, i)), Long.parseLong(num.substring(i, j)), j);
            }
        }
        return result;
    }   
    
    private boolean backtrace(String num, long first, long second, int idx){
        if(idx >= num.length()) return true;
        long sum = first + second;
        if(sum != 0 && num.substring(idx).startsWith("0")) return false;
        else{
            boolean temp = false;
            if(num.substring(idx).startsWith("" + sum)){
                temp |= backtrace(num, second, sum, idx + ("" + sum).length());
            }
            return temp;
        }
    }
}