Bruteforce/BackTracking/DFS Algorithm to Split Array into Fibonacci Sequence


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 <= S.length <= 200
S contains only digits.

Bruteforce and Back Tracking Algorithm to Split String into Fibonacci Numbers

The start of the Fiboancci Numbers can be obtained via Bruteforce algorithms in O(N^2). Once we determine the first two numbers, we can start backtracking searching in the rest of of the string.

We also need to make sure the numbers in the sequence are smaller than the 32-bit signed integer (231-1). Once the search reaches the end and matches the current Fiboancci number, we can simply return the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};
class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};

When we do the back tracking, we can discard current search branch if the current number in the Fiboancci does not appear at the begin of the string. Instead of String.startsWith or IndexOf checks, we can use substring to get the same length of the begining of the string and compare the equality. If the string is itself the current number of Fibonacci number, we have found a good path – then we need to return true.

Also, we need to make sure the numbers does not start with ‘0’ except the number ‘0’ itself. The runtime complexity is O(N^3).

Depth First Search Algorithm to Split a Fibonacci String into Sequences

We can perform a DFS (Depth First Search) Algorithm, and invalidate the current search if by any time, we see the last 3 items (if array length is more than 2) are not Fibonacci Sequences. We also need to skip the searches with leading zeros except it is zero. Also, need to skip the numbers which are bigger than 2^31-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def dfs(index, cur):
            if len(cur) >= 3:
                if cur[-1] != cur[-2] + cur[-3]:
                    return []
            if index == len(S):
                if len(cur) >= 3:
                    return cur
                return []
            for i in range(index, len(S)):
                p = S[index:i+1]
                v = int(p)
                if v == 0 and len(p) > 1:
                    continue
                if len(p) > 1 and p[0] == '0':
                    continue
                if v >= (2<<31-1):
                    continue
                n = cur + [v]
                a = dfs(i + 1, n)
                if len(a) > 0:
                    return a  
                n.pop()                
            return []
        return dfs(0, [])
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        def dfs(index, cur):
            if len(cur) >= 3:
                if cur[-1] != cur[-2] + cur[-3]:
                    return []
            if index == len(S):
                if len(cur) >= 3:
                    return cur
                return []
            for i in range(index, len(S)):
                p = S[index:i+1]
                v = int(p)
                if v == 0 and len(p) > 1:
                    continue
                if len(p) > 1 and p[0] == '0':
                    continue
                if v >= (2<<31-1):
                    continue
                n = cur + [v]
                a = dfs(i + 1, n)
                if len(a) > 0:
                    return a  
                n.pop()                
            return []
        return dfs(0, [])

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
805 words
Last Post: How to Avoid Paying Too Much Fee when Cashing out Bitcoin via Wirex Credit Card?
Next Post: Javascript Function to Detect Capital String

The Permanent URL is: Bruteforce/BackTracking/DFS Algorithm to Split Array into Fibonacci Sequence

Leave a Reply