You are given a string s that consists of only digits.

Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.


	For example, the string s = "0090089" can be split into ["0090", "089"] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
	Another example, the string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0", "0", "1"]. However all the ways are invalid because they have numerical values [0,1], [0,1], and [0,0,1] respectively, all of which are not in descending order.


Return true if it is possible to split s​​​​​​ as described above, or false otherwise.

A substring is a contiguous sequence of characters in a string.

&nbsp;
Example 1:

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.


Example 2:

Input: s = "050043"
Output: true
Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.


Example 3:

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 20
	s only consists of digits.


class Solution:
    def splitString(self, s: str, last_val: int = None) -> bool:
        # Base case, remaining string is a valid solution
        if last_val and int(s) == last_val - 1:
            return True

        # Iterate through increasingly larger slices of s
        for i in range(1, len(s)):
            cur = int(s[:i])
            # If current slice is equal to last_val - 1, make
            # recursive call with remaining string and updated last_val
            if last_val is None or cur == last_val - 1:
                if self.splitString(s[i:], cur):
                    return True

        return False
class Solution {
    public boolean splitString(String s) {
        return isRemainingValid(s, null);
    }
    private boolean isRemainingValid(String s, Long previous) {
        long current =0;
        for(int i=0;i<s.length();i++) {
            current = current * 10 + s.charAt(i)-'0';
            if(current >= 10000000000L) return false;   // Avoid overflow
            if(previous == null) {
                if (isRemainingValid(s.substring(i+1), current)) 
                    return true;
            } else if(current == previous - 1 && (i==s.length()-1 || isRemainingValid(s.substring(i+1), current)))
                return true;
        }
        return false;
    }
}
class Solution {
    bool helper(string s, long long int tar) {
        if (stoull(s) == tar) return true;
        for (int i = 1; i < s.size(); ++i) {
            if (stoull(s.substr(0, i)) != tar)    continue;
            if (helper(s.substr(i, s.size()-i), tar-1))
                return true;
        }
        return false;
    }
public:
    bool splitString(string s) {
        for (int i = 1; i < s.size(); ++i) {
            long long int tar = stoull(s.substr(0, i));
            if (helper(s.substr(i, s.size()-i), tar-1))
                return true;
        }
        return false;
    }
};
/**
 * @param {string} s
 * @return {boolean}
 */
var splitString = function(s) {

    const backtracking = (index, prevStringValue) => {
        if(index === s.length) {
            return true;
        }
        for(let i = index; i < s.length; i++) {
            const currStringValue = s.slice(index ,i + 1);

            if(parseInt(prevStringValue, 10) === parseInt(currStringValue, 10) + 1) {
                if(backtracking(i + 1, currStringValue)) {
                    return true;
                }
            }
        }
    }
    // we need to have at least two values to compare, so we start with the for outside the backtracking function
    for (let i = 1; i <= s.length - 1; i++) {
        const currStringValue = s.slice(0, i);
        if (backtracking(i, currStringValue)) {
            return true;
        }
    }
    return false
};
Splitting a String Into Descending Consecutive Values