# Simple C++ Recursion Solution

• ``````class Solution {
private:
bool helper(string num, vector<int>& chosen) {
int n = chosen.size() - 1;
if(num.empty()) return (n >= 2) && (chosen[n-2] + chosen[n-1] == chosen.back());
for(int i = 1; i <= num.length(); i++) {
if(i>1 && num.substr(0,i)[0] == '0') continue;
int a = chosen[n-1], b= chosen.back();
if(atoi(num.substr(0,i).c_str()) == a+b) {
chosen.push_back(atoi(num.substr(0,i).c_str()));
bool tmp = helper(num.substr(i, num.length()-i), chosen);
if(!tmp) chosen.pop_back();
else return true;
}
}
return false;
}
public:
if(num.empty() || num.length() < 3) return false;
vector<int> chosen;
for(int i = 1; i <= num.size()/2; ++i) {
if(i>1 && num.substr(0,i)[0] == '0') continue;
for(int j = 1; j <= (num.size()-i)/2; ++j) {
if(j>1 && num.substr(i,j)[0] == '0') continue;
chosen.push_back(atoi(num.substr(0,i).c_str()));
chosen.push_back(atoi(num.substr(i,j).c_str()));
if(helper(num.substr(i+j), chosen)) return true;
}
}
return false;
}
};

``````

• ``````bool isAdditiveNumber(string num) {
int n=num.size();
for(int i=1;i<=n/2;i++) {
for(int j=1;j<=(n-i)/2;j++) {
//if(isValid(i, j, num))
if(isValid(num.substr(0, i), num.substr(i, j), num))
return true;
}
}
return false;
}
bool isValid(string num1, string num2, string& num) {
int i = num1.size();
int j = num2.size();
if (i > 1 && num1[0] == '0') return false;
if (j > 1 && num2[0] == '0') return false;
long long x=stoi(num1);
long long y=stoi(num2);
//cout<<x<<" "<<y<<endl;
string sum="";
for(int start=i+j; start<num.size();start+=sum.size()) {
y=x+y;
x=y-x;
sum=to_string(y);
//cout<<sum<<endl;
//cout<<num.substr(start, sum.size())<<endl;
if(num.substr(start, sum.size())!=sum)
return false;
}
return true;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.