Split a Numeric String into Fibonacci Sequence | C ++ program of the above approach ; Function that returns true if Fibonacci sequence is found ; Base condition : If pos is equal to length of S and seq length is greater than 3 ; Return true ; Stores current number ; Add current digit to num ; Avoid integer overflow ; Avoid leading zeros ; If current number is greater than last two number of seq ; If seq length is less 2 or current number is is equal to the last two of the seq ; Add to the seq ; Recur for i + 1 ; Remove last added number ; If no sequence is found ; Function that prints the Fibonacci sequence from the split of string S ; Initialize a vector to store the sequence ; Call helper function ; If sequence length is greater than 3 ; Print the sequence ; If no sequence is found ; Print - 1 ; Driver Code ; Given String ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define LL  long long NEW_LINE bool splitIntoFibonacciHelper ( int pos , string S , vector < int > & seq ) { if ( pos == S . length ( ) and ( seq . size ( ) >= 3 ) ) { return true ; } LL num = 0 ; for ( int i = pos ; i < S . length ( ) ; i ++ ) { num = num * 10 + ( S [ i ] - '0' ) ; if ( num > INT_MAX ) break ; if ( S [ pos ] == '0' and i > pos ) break ; if ( seq . size ( ) > 2 and ( num > ( ( LL ) seq . back ( ) + ( LL ) seq [ seq . size ( ) - 2 ] ) ) ) break ; if ( seq . size ( ) < 2 or ( num == ( ( LL ) seq . back ( ) + ( LL ) seq [ seq . size ( ) - 2 ] ) ) ) { seq . push_back ( num ) ; if ( splitIntoFibonacciHelper ( i + 1 , S , seq ) ) return true ; seq . pop_back ( ) ; } } return false ; } void splitIntoFibonacci ( string S ) { vector < int > seq ; splitIntoFibonacciHelper ( 0 , S , seq ) ; if ( seq . size ( ) >= 3 ) { for ( int i : seq ) cout << i << " ▁ " ; } else { cout << -1 ; } } int main ( ) { string S = "11235813" ; splitIntoFibonacci ( S ) ; return 0 ; }