累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

分析
只要前两个数字确定了，那么后续的数字相加就是确定的。所以，题目就是在找出合适的前两个数字，并判断最终结果。
在找前两个数时，使用两次for循环就可以了，回溯算法？也可以这么说吧。

实现

1. 处理字符串数字相加

bool add(const string &s, int first, int second, int third) {
        if (third >= s.length()) {
            return true;
        }
        int i = second - 1, j = third - 1;
        int jw = 0;
        string tmp;
        string base = "0123456789";
        while (i >= first && j >= second) {
            int t = s[i] - '0' + s[j] - '0' + jw;
            if (t >= 10) {
                jw = 1;
                t -= 10;
            } else {
                jw = 0;
            }
            tmp.insert(tmp.begin(), base[t]);
            --i;
            --j;
        }
        while (i >= first) {
            int t = s[i] - '0' + jw;
            if (t >= 10) {
                jw = 1;
                t -= 10;
            } else {
                jw = 0;
            }
            tmp.insert(tmp.begin(), base[t]);
            --i;
        }
        while (j >= second) {
            int t = s[j] - '0' + jw;
            if (t >= 10) {
                jw = 1;
                t -= 10;
            } else {
                jw = 0;
            }
            tmp.insert(tmp.begin(), base[t]);
            --j;
        }
        if (jw) {
            tmp.insert(tmp.begin(), base[jw]);
        }
        if (s.substr(third, tmp.length()) !=  tmp) {
            return false;
        }
        return add(s, second, third, third + tmp.length());
    }

2. 确定前两个数

bool isAdditiveNumber(string num) {
        int size = num.length();
        if (size < 3) {
            return false;
        }
        for (int second = 1; second < size; ++second) {
            if (second > 1 && num[0] == '0') {
                return false;
            }
            for (int third = second + 1; third < size; ++third) {
                if (third - second > 1 && num[second] == '0') {
                    break;
                }
                if (add(num, 0, second, third)) {
                    return true;
                }
            }
        }
        return false;
    }

程序中的一个坑点在于，不能出现除0之外以0开头的数字串，如03是不正确的。所以在for循环中需要考虑这种情况。