【LeetCode】306.累加数（思路+题解）

记录个人解题思路与代码，欢迎和谐讨论

一、题目

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

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

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

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

来源：力扣（LeetCode）
链接：源力扣地址

示例 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

提示：

1 <= num.length <= 35
num 仅由数字（0 - 9）组成

二、思路

这道题的解法是经典的回溯算法，回溯算法类似与枚举的搜索尝试，主要是在搜索尝试中寻找问题的解。在本题中，我们设两个待加数字为a与b，结果为c，那么在此问题中搜索即是搜索a与b，尝试判断其是否等于c。在提示中题目强调了num字符串的最长长度为35，那么就意味着可以出现长度为17的数字，其大小远大于int类型支持的位数，因此在算法中采用 long long int类型来保存过程中出现的数字。

除此之外，在问题中强调不会出现以0开头的数字，那么就要求在此之中必须能够判断字符串转出来的数字是否合法。由于在问题中可以看出不会出现复数，那么我们可以通过编写一个字符串转long long int 的函数顺便判断了这个数字是否合法，非法则返回-1.

随后在判断中，如遇到a+b>c的情况，可能是由于进位产生的，因此我们再给c补一位再重新判断是否相等，若a+b<c则显然是出现了搜索错误，因此直接将b的长度++进行新一轮搜索即可。

最后看看效果：

三、代码

代码如下：

class Solution {
    
private:
    long long int getNum(const string num, int pos, int len) {
          //字符串转ll数字，如果非法返回-1;
        if (pos != 0 and len != 1 and num[pos] == '0')
            return -1;
        return stoll(num.substr(pos, len), NULL, 10);
    }
public:
    bool isAdditiveNumber(string num) {
    
        if (num.size() < 3)    return 0;
        int a_len = 1;
        bool a_f = true;
        while (a_len <= floor(num.size() / 2) and a_f) {
    
            int a_pos = 0;
            int b_pos = a_pos + a_len;
            int b_len = 1;
            bool b_f = true;
            while (b_len <= floor((num.size() - a_len) / 2) and a_f and b_f) {
    
                int c_pos = b_pos + b_len;
                int c_len = max(a_len, b_len);
				bool c_f = true;
                long long int a = getNum(num, a_pos, a_len);
                if (a == -1) {
    
                    a_f = false;
                    break;
                }
                long long int b = getNum(num, b_pos, b_len);
                if (b == -1) {
    
                    b_f = false;
                    break;
                }
                int a_len_temp = a_len;
                int b_len_temp = b_len;
				while (c_pos + c_len <= num.size()) {
    
					if (c_len > (max(a_len_temp, b_len_temp) + 1) and c_f) 
						break;
					long long int c = getNum(num, c_pos, c_len);
					if (c == -1) {
    
						c_f = false;
						break;
					}
					if (a + b == c) {
    
                        a = b;
                        b = c;
                        a_len_temp = b_len_temp;
                        b_len_temp = c_len;
                        c_pos = c_pos + c_len;
					}
                    else if (a + b > c) 
                        ++c_len;
                    else if (a + b < c) 
                        break;
                    if (c_pos == num.size())
                        return 1;
				}
                ++b_len;
            }
            ++a_len;
        }
        return 0;
    }
};