LeetCode 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. For example: "112358" is an additive number because 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

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid. Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number. Follow up: How would you handle overflow for very large input integers?

---

给定一个数字字符串，问这个字符串是否是可加的数。一个可加的数是指它可以分割成若干个字符串，每个字符串代表一个数，且这个数列满足斐波那契数列的规律，即后一个数等于前两个数之和。 明显的DFS题。从起点枚举所有可能的长度，转换成数字，然后判断是否等于前两个数字之和。 需要注意的是数组至少要有3个数，且每个数不能有前导0。另外字符串可能很长，导致转换成的数超过int范围，所以用long long和atoll函数。 代码如下： [cpp] typedef long long LL; class Solution { private: bool dfs(const string& num, int start, LL last1, LL last2, int cnt) { int n = num.size(); if (start == n&&cnt >= 3)return true; //if (start < n&&num[start] == ‘0’)return false; // "101" is true int m = num.size() – start; // left length bool ans = false; for (int i = 1; i <= m; ++i) { if (i != 1 && num[start] == ‘0’)continue; // leading zero LL sum = atoll(num.substr(start, i).c_str()); if (cnt >= 2) { if (last1 + last2 > sum)continue; else if (last1 + last2 < sum)return false; else ans = dfs(num, start + i, last2, sum, cnt + 1); } else if (cnt == 0)ans = dfs(num, start + i, sum, last2, cnt + 1); else if(cnt==1)ans= dfs(num, start + i, last1, sum, cnt + 1); if (ans)return true; } return false; } public: bool isAdditiveNumber(string num) { return dfs(num, 0, 0, 0, 0); } }; [/cpp] 本代码提交AC，用时0MS。]]>