Addictive Number
这个solution非常暴力，思想就是从头开始找。。。懒得写了，睡一觉再说吧😂哈哈哈哈
class Solution {
public:
bool isAdditiveNumber(string num) {
for (int i = 1; i <= num.size() / 2; i++)
for (int j = 1; j <= (num.size() - i) / 2; j++)
if (check(num.substr(0, i), num.substr(i, j), num.substr(i + j))) return true;
return false;
}
private:
bool check(string num1, string num2, string num) {
if ((num1.size() > 1 && num1[0] == '0') or (num2.size() > 1 && num2[0] == '0')) return false;
auto sum = add(num1, num2);
if (sum == num) return true;
if (num.size() <= sum.size() or sum != num.substr(0, sum.size())) return false;
else return check(num2, sum, num.substr(sum.size()));
}
string add(string s1, string s2) {
string res;
int carry(0);
int i(s1.size() - 1), j(s2.size() - 1);
while (i >= 0 || j >= 0) {
int sum = carry + ((i >= 0) ? (s1[i--] - '0') : 0) + ((j >= 0) ? (s2[j--] - '0') : 0);
res.push_back((sum % 10) + '0');
carry = sum / 10;
}
if (carry) res.push_back(carry + '0');
reverse(res.begin(), res.end());
return res;
}
};
