题解 | #累加序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr string字符串
     * @return bool布尔型
     */
    public boolean AdditiveArray (String arr) {
        return dfs(arr, arr.length(), 0, 0, 0, 0);
    }

    //利用递归不断找到合适的字符串转成数值满足要求
    public boolean dfs(String s, int n, int index, long sum, long pre, int k) {
        if (index == n ) return k > 2; //k大于2符合题目要求
        for (int i = index; i < n ; i++) {
            int left = index, right = i;
            if (left < right && s.charAt(left) == '0') continue;

            long cur = 0;
            while (left <= right) {
                cur = cur * 10 + (s.charAt(left++) - '0');
            }

            if (k >= 2 && cur != sum) continue;

            if (dfs(s, n, i + 1, cur + pre, cur, k + 1)) return true;
        }

        return false;
    }
}