Split a Numeric String into Fibonacci Sequence | Java 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
import java . util . * ; class GFG { static boolean splitIntoFibonacciHelper ( int pos , String S , ArrayList < Long > seq ) { if ( pos == S . length ( ) && ( seq . size ( ) >= 3 ) ) { return true ; } long num = 0 ; for ( int i = pos ; i < S . length ( ) ; i ++ ) { num = num * 10 + ( S . charAt ( i ) - '0' ) ; if ( num > Integer . MAX_VALUE ) break ; if ( S . charAt ( pos ) == '0' && i > pos ) break ; if ( seq . size ( ) > 2 && ( num > ( ( long ) seq . get ( seq . size ( ) - 1 ) + ( long ) seq . get ( seq . size ( ) - 2 ) ) ) ) break ; if ( seq . size ( ) < 2 || ( num == ( ( long ) seq . get ( seq . size ( ) - 1 ) + ( long ) seq . get ( seq . size ( ) - 2 ) ) ) ) { seq . add ( num ) ; if ( splitIntoFibonacciHelper ( i + 1 , S , seq ) ) return true ; seq . remove ( seq . size ( ) - 1 ) ; } } return false ; } static void splitIntoFibonacci ( String S ) { ArrayList < Long > seq = new ArrayList < > ( ) ; splitIntoFibonacciHelper ( 0 , S , seq ) ; if ( seq . size ( ) >= 3 ) { for ( int i = 0 ; i < seq . size ( ) ; i ++ ) System . out . print ( seq . get ( i ) + " ▁ " ) ; } else { System . out . print ( " - 1" ) ; } } public static void main ( String [ ] args ) { String S = "11235813" ; splitIntoFibonacci ( S ) ; } }