Simple C++ Recursion Solution


  • 0
    X
    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:
        bool isAdditiveNumber(string num) {
            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;
        }
    };
    
    

  • 0
    C
    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;
    }

Log in to reply
 

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