recursive solution c++


  • 0
    U
    class Solution {
    private:
        string nums;
        int length;
        string::size_type sz;
        
    public:
        bool isAdditiveNumber(string num) {
            this->nums = num;
            this->length = this->nums.length();
            if (this->length < 3) return false;
            
            for (int i=0; i < this->length; i++) {
                for (int j=i+1; j < this->length-1; j++) {
                    if (_isAdditiveNumber(-1, i, j)) {
                        return true;
                    }
                    if (stoull(nums.substr(i+1, j-i), nullptr) == 0) break;    
                }
                if (stoull(nums.substr(0, i+1), nullptr) == 0) return false; 
            }
            return false;
        }
    
    private:
        bool _isAdditiveNumber(
            int left_border, 
            int first_index, 
            int second_index) 
        {
            if (second_index == length - 1) {
                return true;
            }
            
            unsigned long long sum=
               stoull(
                  nums.substr(left_border+1, first_index-left_border), 
                  nullptr
               ) + stoull(
                  nums.substr(first_index+1, second_index-first_index),
                  nullptr
               );
            
            int offset = 1;
            unsigned long long nextSum = stoull(
               nums.substr(second_index+1, offset), 
               nullptr
            );
            if (sum != 0 && nextSum == 0) {
                return false;
            }       
           
            while(second_index + offset < length && sum > nextSum) {
                offset++;
                nextSum = stoull(nums.substr(second_index+1, offset), nullptr);
            }
            
            if (sum == stoull(nums.substr(second_index+1, offset), nullptr)) {
                return _isAdditiveNumber(
                      first_index,
                      second_index, 
                      second_index + offset
                );
            }
            return false;
        }
    };
    
    

Log in to reply
 

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