累加數是一個字符串，組成它的數字可以形成累加序列。

一個有效的累加序列必須至少包含 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

解題思路

字符串實現大數相加，保證了不會溢出

代碼

class Solution {boolean isa=false;public boolean isAdditiveNumber(String num) {additiveNumber(num,0,new ArrayList<>());return isa;}public String  sadd(String num1,String num2) {//字符串相加int carry=0;int n=num1.length()-1,m=num2.length()-1;StringBuilder strijavangBuilder=new StringBuilder();while (n>=0||m>=0||carry>0){int o1=n>=0?num1.charAt(n)-'0':0;int o2=m>=0?num2.charAt(m)-'0':0;stringBuilder.append((char)((carry+o1+o2)%10+'0'));carry=(carry+o1+o2)>=10?1:0;n--;m--;}return stringBuilder.reverse().toString();}public void additiveNumber(String num,int pos,List<String> temp) {if(pos==num.length())//遍歷到了末尾{if(temp.size()>=3)isa=true;return ;}for(int len=1;len+pos<=num.length();len++){if(isa) break;String s=num.substring(pos,pos+len);if(s.length()>1&&s.charAt(0)=='0') continue;if(temp.size()>=2){if(sadd(temp.get(temp.size()-1),temp.get(temp.size()-2)).equals(s))//判斷是否相等{temp.add(s);additiveNumber(num, pos+len, temp);temp.remove(temp.size()-1);//回溯}}else{//不夠3個數就直接加進去temp.add(s);additiveNumber(num, pos+len, temp);temp.remove(temp.size()-1);}}}
}