Skip to content

842. Split Array into Fibonacci Sequence

  • Time: $O(n^2)$
  • Space: 
 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
class Solution {
 public:
  vector<int> splitIntoFibonacci(string num) {
    vector<int> ans;
    dfs(num, 0, ans);
    return ans;
  }

 private:
  bool dfs(const string& num, int s, vector<int>& ans) {
    if (s == num.length() && ans.size() >= 3)
      return true;

    for (int i = s; i < num.length(); ++i) {
      if (num[s] == '0' && i > s)
        break;
      const long val = stol(num.substr(s, i + 1 - s));
      if (val > INT_MAX)
        break;
      if (ans.size() >= 2 &&
          val > ans[ans.size() - 2] + static_cast<long>(ans.back()))
        break;
      if (ans.size() <= 1 ||
          val == ans[ans.size() - 2] + static_cast<long>(ans.back())) {
        ans.push_back(val);
        if (dfs(num, i + 1, ans))
          return true;
        ans.pop_back();
      }
    }

    return false;
  }
};

 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
class Solution {
  public List<Integer> splitIntoFibonacci(String num) {
    List<Integer> ans = new ArrayList<>();
    dfs(num, 0, ans);
    return ans;
  }

  private boolean dfs(final String num, int s, List<Integer> ans) {
    if (s == num.length() && ans.size() >= 3)
      return true;

    for (int i = s; i < num.length(); ++i) {
      if (num.charAt(s) == '0' && i > s)
        break;
      final long val = Long.valueOf(num.substring(s, i + 1));
      if (val > Integer.MAX_VALUE)
        break;
      if (ans.size() >= 2 && val > ans.get(ans.size() - 2) + ans.get(ans.size() - 1))
        break;
      if (ans.size() <= 1 || val == ans.get(ans.size() - 2) + ans.get(ans.size() - 1)) {
        ans.add((int) val);
        if (dfs(num, i + 1, ans))
          return true;
        ans.remove(ans.size() - 1);
      }
    }

    return false;
  }
}