842. Split Array into Fibonacci Sequence #

Problem #

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1. 1 <= S.length <= 200
2. S contains only digits.

Problem Summary #

Given a numeric string S, such as S = “123456579”, we can split it into a Fibonacci-like sequence [123, 456, 579]. A Fibonacci-like sequence is a list F of non-negative integers satisfying:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• For all 0 <= i < F.length - 2, F[i] + F[i+1] = F[i+2] holds.

In addition, note that when splitting the string into pieces, each piece must not start with zero, unless the piece is the number 0 itself. Return all Fibonacci-like sequence pieces split from S; if it cannot be split, return [].

Solution Approach #

• This problem is an enhanced version of Problem 306. Problem 306 asks to determine whether a string satisfies the form of a Fibonacci sequence. This problem asks to output the numeric array after splitting according to the form of a Fibonacci sequence.
• The idea for this problem is basically the same as Problem 306. What needs attention is one constraint in the problem: 0 <= F[i] <= 2^31 - 1. Pay attention to this condition. I did not notice it at first, and the output solution was wrong later. You can look at the last two sets of data in my test file cases. Both of these can be decomposed into Fibonacci sequences, but since the numbers after splitting are all greater than 2^31 - 1, these solutions cannot be accepted!
• This problem also requires special attention to pruning conditions. Without pruning conditions, the time complexity is extremely high. With reasonable pruning conditions, it passes in 0ms.

Code #

package leetcode

import (
	"strconv"
	"strings"
)

func splitIntoFibonacci(S string) []int {
	if len(S) < 3 {
		return []int{}
	}
	res, isComplete := []int{}, false
	for firstEnd := 0; firstEnd < len(S)/2; firstEnd++ {
		if S[0] == '0' && firstEnd > 0 {
			break
		}
		first, _ := strconv.Atoi(S[:firstEnd+1])
		if first >= 1<<31 { // The problem requires every number to be less than 2^31 - 1 = 2147483647; pruning here is crucial!
			break
		}
		for secondEnd := firstEnd + 1; max(firstEnd, secondEnd-firstEnd) <= len(S)-secondEnd; secondEnd++ {
			if S[firstEnd+1] == '0' && secondEnd-firstEnd > 1 {
				break
			}
			second, _ := strconv.Atoi(S[firstEnd+1 : secondEnd+1])
			if second >= 1<<31 { // The problem requires every number to be less than 2^31 - 1 = 2147483647; pruning here is crucial!
				break
			}
			findRecursiveCheck(S, first, second, secondEnd+1, &res, &isComplete)
		}
	}
	return res
}

//Propagate for rest of the string
func findRecursiveCheck(S string, x1 int, x2 int, left int, res *[]int, isComplete *bool) {
	if x1 >= 1<<31 || x2 >= 1<<31 { // The problem requires every number to be less than 2^31 - 1 = 2147483647; pruning here is crucial!
		return
	}
	if left == len(S) {
		if !*isComplete {
			*isComplete = true
			*res = append(*res, x1)
			*res = append(*res, x2)
		}
		return
	}
	if strings.HasPrefix(S[left:], strconv.Itoa(x1+x2)) && !*isComplete {
		*res = append(*res, x1)
		findRecursiveCheck(S, x2, x1+x2, left+len(strconv.Itoa(x1+x2)), res, isComplete)
		return
	}
	if len(*res) > 0 && !*isComplete {
		*res = (*res)[:len(*res)-1]
	}
	return
}