306.累加数

 

class Solution {
public:
	bool isAdditiveNumber(string num) {
		string first, second,last;
		for (int len1 = 1; len1 <= num.size() / 2; len1++)
		{
			first = num.substr(0,len1);
			for (int len2 = 1; len2 <= num.size() / 2; len2++)
			{
				second = num.substr(len1, len2);
				last = num.substr(len1 + len2, num.size() - len1 - len2);
				if (dfs(first, second, last))
					return true;
			}
			
		}
		return false;
	}
	bool dfs(string first, string second, string last)
	{
		bool flag = true;
		if (first[0] == '0'&&first != "0" || second[0] == '0'&&second != "0")
			return false;
		string s = add(first, second);
		if (s.size() > last.size())
			return false;
		else if (s.size() == last.size())
		{
			if (s.compare(last) == 0)
				return true;
			else
				return false;
		}
		else
		{
			string temp=last.substr(0,s.size());
			if (temp.compare(s) != 0)
				return false;
			else
			{
				first = second;
				second = s;
				int size = s.size();
				last = last.substr(size, last.size() - size);
				flag=dfs(first, second, last);
			}
		}
		return flag;
	}
	string add(string first, string second)
	{
		if (first.size() < second.size())
			swap(first, second);
		int carry = 0;
		int i, j;
		string s="";
		j = second.size() - 1;
		i = first.size() - 1;
		int t1, t2;
		while (j >= 0)
		{
			t1 = first[i--] - '0';
			t2 = second[j--] - '0';
			int sum = t1 + t2 + carry;
			char t = (sum % 10) + '0';
			s += t;
			carry = sum / 10;
		}
		while (i >= 0)
		{
			t1 = first[i--] - '0';
			int sum = t1 + carry;
			char t = (sum % 10) + '0';
			s += t;
			carry = sum / 10;
		}
		if (carry)
		{
			char t = carry + '0';
			s += t;
		}
		reverse(s.begin(), s.end());
		for (int i = 0; i < s.size(); i++)
			cout << s[i];
		cout << endl;
		return s;
			
	}
};