306. 累加数

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

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

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

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

示例 1:

输入: "112358"
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:

输入: "199100199"
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
进阶:
你如何处理一个溢出的过大的整数输入?

这道题难是确实不难的，但是处理字符串的输出处理大数相加，要吐血了，一开始以为long就够了，后面测试用例告诉我太年轻了。
代码调试了很久，改了又改，很多特殊情况都需要考虑。
思路是简单的，无非就是先通过回溯来确定前两个数，当确定了前两个数，就可以直接进行剪枝判断了，后面的所有数都是确定的，如果不符合累加序列则直接返回。
关键是大数相加，需要用字符串来保存，是比较复杂的。
代码如下:

class Solution {
        boolean ans = false;
        public boolean isAdditiveNumber(String num) {
            traceback(num,0,"0","0",0);
            return ans;
        }
        void traceback(String num, int start,String first,String second,int n){
            if (start == num.length()){
                if (n >= 3)
                    ans = true;
                return ;
            }
            if (ans == true) return;
            if ( n < 2 ){
                if (num.charAt(start) == '0'){
                    traceback(num,start+1,second,"0",n+1);
                }
                else{
                    for (int i = start + 1; i < num.length(); i++){
                        String newSecond = num.substring(start,i);
                        traceback(num,i,second,newSecond,n+1);
                    }
                }
            }
            else {
                String sum = add(first,second);
                int bit = sum.length();
                if (start + bit > num.length())
                    return ;
                String s = num.substring(start,start+ bit);
                if ( !sum.equals(s))
                    return ;
                traceback(num,start+bit,second,sum,n+1);
            }
        }
        String add(String first,String second){
            String sum ="";
            int carry = 0;
            for (int i = first.length() - 1,j = second.length() - 1; i >=0 || j >=0; i--,j--){
                int num1 = i >= 0 ? first.charAt(i)-'0' : 0;
                int num2 = j >= 0 ? second.charAt(j)-'0' : 0;

                int s = num1 + num2 + carry;
                carry = s / 10;
                sum = s % 10 + sum;
            }
            if (carry != 0) sum = 1 + sum;
            return sum;

        }
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/additive-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。