842. Split Array into Fibonacci Sequence

问题：

给定由数字构成的字符串，对其进行分割，使得构成斐波那契数列。

返回一个解。

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.

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.

解法：Backtracking（回溯算法）

状态：字符串当前位置pos为止，构成的解path。
选择：下一个子串s[pos~i~S.size]，
- 若path还不满2个子串：选择第1，2子串：　　
  - 任意长度可选。　　　　
- 若path超过2个子串：选择第3...子串：　　　　
  - 子串==path尾部两个子串之和。
退出递归条件：
- 当前位置pos==S.size
  - 加入res：path.size>2
  - 不加res：path.size<=2
其他退出：
- 第1，2子串：
  - >INT_MAX or　　　　
  - <0 or　　　　
  - 首字母='0'且该子串转成数字!=0　　　　
- 第3...子串：　　
  - >INT_MAX or　　　　
  - !=前两个子串之和

代码参考：

 1 class Solution {
 2 public:
 3     void getres(vector<int>& res, vector<string>& path) {
 4         if(path.size()<=2) return;
 5         for(string p:path) {
 6             res.push_back(atoi(p.c_str()));
 7         }
 8         return;
 9     }
10     void dfs(vector<int>& res, string S, int pos, vector<string>& path) {
11         if(pos==S.length()) {
12             getres(res, path);
13             return;
14         }
15         int i = 1;
16         int n = path.size();
17         long long curres = 0;
18         if(n>=2) {
19             curres = atoll(path[n-1].c_str()) + atoll(path[n-2].c_str());
20             if(curres >= INT_MAX) return;
21             i = to_string(curres).length();
22             string num = S.substr(pos, i);
23             int numi = atoi(num.c_str());
24             if(numi!=curres) return;
25             else {
26                 path.push_back(num);
27                 dfs(res, S, pos+i, path);
28                 path.pop_back();
29                 return;
30             }
31         } else {
32             for(i; i<=S.length()-pos; i++) {
33                 string num = S.substr(pos, i);
34                 int numi = atoi(num.c_str());
35                 if(numi >= INT_MAX || numi < 0 || (num[0] == '0' && num.length() != 1)) break;
36                 path.push_back(num);
37                 dfs(res, S, pos+i, path);
38                 if(!res.empty()) return;
39                 path.pop_back();
40             }
41         }
42         
43     }
44     vector<int> splitIntoFibonacci(string S) {
45         vector<int> res;
46         vector<string> path;
47         dfs(res, S, 0, path);
48         return res;
49     }
50 };