leetcode 842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列

Problem: 842. Split Array into Fibonacci Sequence 将数组拆分成斐波那契序列

解题过程

回溯，每次保存前一个、前前一个数字，判断分割的数字是否符合条件，已经数字是否是0，或是不满足条件的多个数字前置0，以及每个数字< INT_MAX，数字<sum扩大，数字>sum返回，数字==sum再递归，满足条件才递归调用，最后判断是否空以及列表长度>=3

Code

class Solution { public: vector<int> tr; bool flag = false; void dfs(string num, long long prepre, long long pre) { if(flag == true) return; if(num.size() == 0 && tr.size() >= 3) { flag = true; return; } string next, now; long long no, sum = prepre + pre; for(int i = 1; i <= num.size(); i++) { now = num.substr(0, i); if(now.size() > 1 && now[0]=='0') continue; no = stoll(now); if(no > INT_MAX) return; if(prepre >= 0) { if(sum > no) { continue; } else if(sum == no) { next = num.substr(i); tr.push_back(no); dfs(next, pre, no); if(flag == true) return; tr.pop_back(); } else { return; } } else { next = num.substr(i); tr.push_back(no); dfs(next, pre, no); if(flag == true) return; tr.pop_back(); } } } vector<int> splitIntoFibonacci(string num) { dfs(num, -1, -1); return tr; } };