LeetCode 1849. 将字符串拆分为递减的连续值（回溯）

示例 1：
输入：s = "1234"
输出：false
解释：不存在拆分 s 的可行方法。

示例 2：
输入：s = "050043"
输出：true
解释：s 可以拆分为 ["05", "004", "3"] ，对应数值为 [5,4,3] 。
满足按降序排列，且相邻值相差 1 。

示例 3：
输入：s = "9080701"
输出：false
解释：不存在拆分 s 的可行方法。

示例 4：
输入：s = "10009998"
输出：true
解释：s 可以拆分为 ["100", "099", "98"] ，对应数值为 [100,99,98] 。
满足按降序排列，且相邻值相差 1 。
 
提示：
1 <= s.length <= 20
s 仅由数字组成

class Solution {
    bool can = false;
public:
    bool splitString(string s) {
        dfs(s, LONG_LONG_MAX, 0);
        return can;
    }
    void dfs(string s, long long prevVal, int ct)
    {
        if(can) return; // 找到解了
        if(s == ""){
            if(ct > 1) // 个数至少为 2
                can = true;
            return;
        }
        long long curVal = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(curVal >= LONG_LONG_MAX/10)
                break; // 当前数字超过范围，肯定不存在解
            // LLMAX : 9223372036854775807, 19位
            curVal = curVal*10 + s[i]-'0';
            if(prevVal - curVal < 1)
                break; // curval 越来越大，不存在降序的
            else if(prevVal == LONG_LONG_MAX || prevVal - curVal == 1)
            {
                dfs(s.substr(i+1), curVal, ct+1);
            }
        }
    }
};