---
# System prepended metadata

title: 2698. Find the Punishment Number of an Integer
tags: [Leetcode, Recursion, Medium]

---

Link: https://leetcode.com/problems/find-the-punishment-number-of-an-integer/description/
## 思路
遍历所有数字 看能不能被partition
canPartition function里面用到recursion
从左到右遍历所有位置作为partition point 左边不拆分 右边recursion拆分 看是否能凑出
## Code
```python=
class Solution:
    def punishmentNumber(self, n: int) -> int:
        def canPartition(sqr, i):
            if i<0: return False
            if i==0 and sqr=="": return True
            left = 0
            for j in range(len(sqr)):
                left = left*10+int(sqr[j])
                if canPartition(sqr[j+1:], i-left): return True
                if left>i: return False
            return False
        ans = 0
        for i in range(1, n+1):
            if canPartition(str(i*i), i):
                ans += i*i
        return ans
```