题目

    给定一个字符串，字符串中的字符均为0-9的数字。判断字符串是否是一个合法的additive序列。additive 序列至少包含3个数字，除了最开始的两个数字，之后所有的数字都必须是它之前两个数字的和。比如字符串 "112358" 分割成 1,1,2,3,5,8 序列，序列从第三个数字开始，每个数字都是它前两个数字的和；字符串 "199100199"分割成序列1,99,100,199，从第三个数字开始，每个数字都是它前面两个数字的和。 

    题目链接:

    很容易想到递归去判断是否是additive 序列，但递归的几个参数如何确定？肯定要有前面两个数字a和 

b，然后还需要字符串去掉a和b之后的子串str，因此，可以有递归函数 isAdditive(ll a, ll b, string str). 

    然后，如何确定递归的入口呢？即a和b如何确定？ 显然，使用0是不合理的，因此，只能枚举合法的a和b，然后再调用递归算法。

实现

typedef long long int ll;class Solution {public:	bool isAdditiveNumber(string num) {		int n = num.length();		for (int i = 1; i <= (n - 1) / 2; i++){			if (num[0] == '0' && i >= 2)				break;			for (int j = i + 1; j - i <= n - j && i <= n - j; j++){				if (num[i] == '0' && j - i >= 2)					break;				ll a = getNum(num, 0, i - 1);				ll b = getNum(num, i, j - 1);				if (helper(a, b, num.substr(j)))					return true;			}		}		return false;	}	ll getNum(string& str, int beg, int end){		ll result = 0;		while (beg <= end){			result *= 10;			result += str[beg] - '0';			beg ++;		}		return result;	}	bool helper(ll a, ll b, string str){		if (str.length() == 0)			return true;		ll c = a + b;		string cstr = to_string(c);		int k = 0;		while (k < cstr.length()){			if (cstr[k] != str[k])				return false;			k++;		}		return helper(b, c, str.substr(k));	}};