题目描述（中等难度）

306、Additive Number

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

Constraints:

• num consists only of digits '0'-'9'.
• 1 <= num.length <= 35

Follow up: How would you handle overflow for very large input integers?

给一个字符串，判断字符串符不符合某种形式。就是从开头选两个数，它俩的和刚好是下一个数，然后第 2 个数和第 3 数字的和又是下一个数字，以此类推。

解法一

理解了题意的话很简单，可以勉强的归到回溯法的问题中，我们从暴力求解的角度考虑。

首先需要两个数，我们可以用两层 for 循环依次列举。

//i 表示第一个数字的结尾(不包括 i)
for (let i = 1; i < num.length; i++) {
    //j 表示从 i 开始第二个数字的结尾(不包括 j)
    for (let j = i + 1; j < num.length; j++) {
        let num1 = Number(num.substring(0, i));
        let num2 = Number(num.substring(i, j));
    }
}

然后需要处理下特殊情况，将以 0 开头但不是0的数字去掉，比如 023 这种是不合法的，

//i 表示第一个数字的结尾(不包括 i) 
for (let i = 1; i < num.length; i++) {
    // 0 开头, 并且当前数字不是 0
    if (num[0] === '0' && i > 1) {
        return false;
    }
    //j 表示从 i 开始第二个数字的结尾(不包括 j)
    for (let j = i + 1; j < num.length; j++) {
        // 0 开头, 并且当前数字不是 0  
        if (num[i] === '0' && j - i > 1) {
            break;
        }
        let num1 = Number(num.substring(0, i));
        let num2 = Number(num.substring(i, j));
    }
}

有了这两个数字，下边的就好说了。

只需要计算 sum = num1 + num2 ，然后看 sum 在不在接下来的字符串中。

如果不在，那么就考虑下一个 num1 和 num2 。

如果在的话，num1 就更新为 num2，num2 更新为 sum ，有了新的 num1和 num2 ，然后继续按照上边的步骤考虑。

举个例子，

1 2 2 1 4 16
    ^ ^
    i j

num1 = 12
num2 = 2
sum = num1 + num2 = 14

接下来的数字刚好是 14, 那么就更新 num1 和 num2

num1 = num2 = 2
num2 = sum = 14

然后继续判断即可。

代码的话，我们可以写成递归的形式。

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
    if (num.length === 0) {
        return true;
    }
    for (let i = 1; i < num.length; i++) {
        if (num[0] === '0' && i > 1) {
            return false;
        }
        for (let j = i + 1; j < num.length; j++) {
            if (num[i] === '0' && j - i > 1) {
                break;
            }
            let num1 = Number(num.substring(0, i));
            let num2 = Number(num.substring(i, j));
            if (isAdditiveNumberHelper(num.substring(j), num1, num2)) {
                return true;
            }
        }
    }
    return false;
};

function isAdditiveNumberHelper(num, num1, num2) {
    if (num.length === 0) {
        return true;
    }
    //依次列举数字，判断是否等于 num1 + num2
    for (let i = 1; i <= num.length; i++) {
        //不考虑以 0 开头的数字
        if (num[0] === '0' && i > 1) {
            return false;
        }
        let sum = Number(num.substring(0, i));
        if (num1 + num2 === sum) {
            //传递剩下的字符串以及新的 num1 和 num2
            return isAdditiveNumberHelper(num.substring(i), num2, sum);
            //此时大于了 num1 + num2, 再往后遍历只会更大, 所以直接结束
        } else if (num1 + num2 < sum) {
            break;
        }
    }
    return false;
}

主要思想就是上边的了，看了 这里 的分析，代码的话，可以简单的优化下。

第一点，如果两个数的位数分别是 a 位和 b 位，a >= b，那么它俩相加得到的和至少是 a 位。比如 100 + 99 得到 199，依旧是三位数。

所以我们的 num1 和 num2 其中的一个数的位数一定不能大于等于字符串总长度的一半，不然的话剩下的字符串一定不等于 num1 和 num2 的和，因为剩下的长度不够了。

第二点，上边的代码中 isAdditiveNumberHelper 函数，略微写的复杂了些，我们可以直接利用 String 的 startsWith 函数，判断 num1 + num2 是不是字符串的开头即可。

基于上边两点，优化后的代码如下。

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
    if (num.length === 0) {
        return true;
    }
    //这里取了等号，是因为长度是奇数的时候，除以二是向下取整
    for (let i = 1; i <= num.length / 2; i++) {
        if (num[0] === '0' && i > 1) {
            return false;
        }
        for (let j = i + 1; j < num.length; j++) {
            if (num[i] === '0' && j - i > 1 || (j - i) > num.length / 2) {
                break;
            }
            let num1 = Number(num.substring(0, i));
            let num2 = Number(num.substring(i, j));
            if (isAdditiveNumberHelper(num.substring(j), num1, num2)) {
                return true;
            }
        }
    }
    return false;
};

function isAdditiveNumberHelper(num, num1, num2) {
    if (num.length === 0) {
        return true;
    }
    return num.startsWith(num1 + num2) && isAdditiveNumberHelper(num.substring((num1+num2+'').length), num2, num1 + num2);
}

当然，我们最初的分析很明显是迭代的形式，我们内层也可以直接写成循环，不需要递归函数。

/**
 * @param {string} num
 * @return {boolean}
 */
var isAdditiveNumber = function (num) {
    if (num.length === 0) {
        return true;
    }
    for (let i = 1; i <= num.length / 2; i++) {
        if (num[0] === '0' && i > 1) {
            return false;
        }
        for (let j = i + 1; j < num.length; j++) {
            if (num[i] === '0' && j - i > 1 || (j - i) > num.length / 2) {
                break;
            }
            let num1 = Number(num.substring(0, i));
            let num2 = Number(num.substring(i, j));
            let temp = num.substring(j);
            while(temp.startsWith(num1 + num2)) {
                let n = num1;
                num1 = num2;
                num2 = num1 + n;
                temp = temp.substring((num2 + '').length);
                if (temp.length === 0) {
                    return true;
                }
            } 
        }
    }
    return false;
};

还有一个扩展，How would you handle overflow for very large input integers?

让我们考虑数字太大了怎么办，此时解决大数相加的问题即可，所有的操作在字符串层面上进行。参考 第 2 题。

总

这道题主要的想法就是列举所有情况，但总觉得先单独列举两个数字不够优雅，思考了下怎么把它合并到递归中，无果，悲伤。

上边其实是一种思路，只是在写法上可能有所不同，唯一的优化就是列举数字的时候考虑一半即可，但时间复杂度不会变化。

之所以说勉强归到回溯法，是因为遍历路径的感觉是，先选两个数，然后一路到底，失败的话不是回到上一层，而是直接回到开头，然后重新选取两个数，继续一路到底，不是典型的回溯。