---

[!info] related notes 算法面试题型 MOC 回溯

求一个整数的惩罚数

题目

2698. 求一个整数的惩罚数 - 力扣（LeetCode）

题解

链表-二叉树-回溯

var punishmentNumber = function (n) {

    // p 的含义是当前是处理下标 p 后的字符串；sum 表示当前情况下前 p 位 的和
    function dfs(p, sum, s, i) {
        const n = s.length;
        if (p === n) {
            return sum === i;
        }
        let x = 0;
        // 增量构造，枚举当前层的每一种可能性
        for (let j = p; j < n; j++) {
            x = x * 10 + parseInt(s[j])
            if (dfs(j + 1, sum + x, s, i)) {
                return true;
            }
        }
        return false;
    }

    const PRE_SUM = new Array(1001).fill(0);
    for (let i = 1; i <= 1000; i++) {
        const s = (i * i).toString();
        PRE_SUM[i] = PRE_SUM[i-1] + (dfs(0, 0, s, i) ? i * i : 0);
    }
    return PRE_SUM[n];
};

参考