來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/additive-number
題目描述:
累加數(shù) 是一個字符串，組成它的數(shù)字可以形成累加序列枝誊。
一個有效的 累加序列 必須 至少 包含 3 個數(shù)况芒。除了最開始的兩個數(shù)以外，字符串中的其他數(shù)都等于它之前兩個數(shù)相加的和叶撒。
給你一個只包含數(shù)字 '0'-'9' 的字符串绝骚，編寫一個算法來判斷給定輸入是否是 累加數(shù) 。如果是祠够，返回 true 压汪；否則，返回 false 古瓤。
說明：累加序列里的數(shù) 不會 以 0 開頭止剖，所以不會出現(xiàn) 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
代碼實現(xiàn):
class Solution {
String num;
int n;
List<List<Integer>> list = new ArrayList<>();
public boolean isAdditiveNumber(String _num) {
num = _num;
n = num.length();
return dfs(0);
}
boolean dfs(int u) {
int m = list.size();
if (u == n) return m >= 3;
int max = num.charAt(u) == '0' ? u + 1 : n;
List<Integer> cur = new ArrayList<>();
for (int i = u; i < max; i++) {
cur.add(0, num.charAt(i) - '0');
if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {
list.add(cur);
if (dfs(i + 1)) return true;
list.remove(list.size() - 1);
}
}
return false;
}
boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
List<Integer> ans = new ArrayList<>();
int t = 0;
for (int i = 0; i < a.size() || i < b.size(); i++) {
if (i < a.size()) t += a.get(i);
if (i < b.size()) t += b.get(i);
ans.add(t % 10);
t /= 10;
}
if (t > 0) ans.add(t);
boolean ok = c.size() == ans.size();
for (int i = 0; i < c.size() && ok; i++) {
if (c.get(i) != ans.get(i)) ok = false;
}
return ok;
}
}
