<p>You are given a string of digits <code>num</code>, such as <code>&quot;123456579&quot;</code>. We can split it into a Fibonacci-like sequence <code>[123, 456, 579]</code>.</p>

<p>Formally, a <strong>Fibonacci-like</strong> sequence is a list <code>f</code> of non-negative integers such that:</p>

<ul>
	<li><code>0 &lt;= f[i] &lt; 2<sup>31</sup></code>, (that is, each integer fits in a <strong>32-bit</strong> signed integer type),</li>
	<li><code>f.length &gt;= 3</code>, and</li>
	<li><code>f[i] + f[i + 1] == f[i + 2]</code> for all <code>0 &lt;= i &lt; f.length - 2</code>.</li>
</ul>

<p>Note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number <code>0</code> itself.</p>

<p>Return any Fibonacci-like sequence split from <code>num</code>, or return <code>[]</code> if it cannot be done.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;1101111&quot;
<strong>Output:</strong> [11,0,11,11]
<strong>Explanation:</strong> The output [110, 1, 111] would also be accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;112358130&quot;
<strong>Output:</strong> []
<strong>Explanation:</strong> The task is impossible.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;0123&quot;
<strong>Output:</strong> []
<strong>Explanation:</strong> Leading zeroes are not allowed, so &quot;01&quot;, &quot;2&quot;, &quot;3&quot; is not valid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 200</code></li>
	<li><code>num</code> contains only digits.</li>
</ul>

class Solution {
public:

    bool possible(long long num1, long long num2, int ind, long long cmpNum, vector<int>&ans, vector<int>&vec,int &len)
    {
        if(ind==len-1)
        {
            if(num1+num2==cmpNum)
            {
                ans.push_back(cmpNum);
                return true;
            }
            else
            {
                return false;
            }
        }
        if(ind>=len)
        {
            return false;
        }
        if(num1 > LLONG_MAX - num2)
        {
            return false;
        }
        
        long long sum=num1+num2;
        if(sum<cmpNum)
        {
            return false;
        }
        if(num1<0 || num2<0 ||  sum<0)
        {
            return false;
        }
        
        if(sum==cmpNum)
        {
            ans.push_back(sum);
            return possible(num2,sum,ind+1,vec[ind+1],ans,vec,len);
        }
        else if(sum>cmpNum)
        {
            if(cmpNum==0)
            {
                return false;  //handle leading zero case
            }
            if (cmpNum > (LLONG_MAX - vec[ind + 1]) / 10) {
                return false;  // Prevent overflow
            }
            if(cmpNum*10+vec[ind+1]>INT_MAX)
            {
                return false;
            }
            int newnum=cmpNum*10+vec[ind+1];
            
            cout<<newnum<<" ";
            if(newnum<0)
            {
                return false;
            }
            return possible(num1,num2,ind+1,newnum,ans,vec,len);
        }
       
        return false;
    }
    vector<int> splitIntoFibonacci(string num) {
        int len=num.length();
       
        vector<int>vec(len+2,0);
         vector<int>ans;
         for (int i = 0; i < len; i++) 
         {
            vec[i] = num[i] - '0';
         }

        long long num1=0;
        int flag=true;
        for(int i=0;i<len;i++)
        {
            if(vec[i]!=0)
            {
                flag=false;
                break;
            }
        }
        if(flag==true)
        {
            ans.resize(len,0);
            return ans;
        }
        bool z=false;
        for(int i=0;i<=len/2;i++)
        {
            if(i==0 && vec[i]==0)
            {
                z=true;
            }
            if(i>0 && z==true)
            {
                break;
            }
            if (num1 > (LLONG_MAX - vec[i]) / 10) {
                break;  // Prevent overflow
            }
            num1=num1*10 + vec[i];
            
            long long num2=0;
            bool flag1=false;
            for(int j=i+1;j<=(i+len/2);j++)
            {
                if(j==i+1 && vec[j]==0)
                {
                    flag1=true;
                }
                if(j>i+1 && flag1==true)
                {
                    break;
                }
                 if (num2 > (LLONG_MAX - vec[j]) / 10) {
                    break;  // Prevent overflow
                }
                num2=num2*10 +vec[j];
                
                ans.push_back(num1);
                ans.push_back(num2);
                cout<<num1<<","<<num2<<endl;
                if(possible(num1,num2,j+1,vec[j+1],ans,vec,len))
                {
                    return ans;
                }
                else
                {
                    ans.clear();
                }
            }
        }
        return {};

    }
};
8600