<p>Given a positive integer <code>n</code>, return <em>the <strong>punishment number</strong></em> of <code>n</code>.</p>

<p>The <strong>punishment number</strong> of <code>n</code> is defined as the sum of the squares of all integers <code>i</code> such that:</p>

<ul>
	<li><code>1 &lt;= i &lt;= n</code></li>
	<li>The decimal representation of <code>i * i</code> can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals <code>i</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 182
<strong>Explanation:</strong> There are exactly 3 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 37
<strong>Output:</strong> 1478
<strong>Explanation:</strong> There are exactly 4 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1. 
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. 
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. 
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution:
    def punishmentNumber(self, n: int) -> int:
        # punishment number n is the sum of the squares of all int i such that
        # 1 <= i <= n
        

        # 1 because 1 * 1 = 1

        # 9 because 9 * 9 = 81, and 8 + 1 == 9

        # 10 because 10 * 10 == 100, and 10 + 0 == 10

        # 36 because 36 * 36 = 1296 and 1 + 29 + 6 = 36


        # we need an outer for loop to go betwee 1 and n inclusive
        # and at each value, check if the number squares, can some how be added within themselves
        # to make it equals to the value again

        # split the target into different portion of the number too
        # target - first tenth, number - first tenth
        # and continue to do so until we find a true

        # For example: Can we split 65536 to sum up to 256? There are 3 choices:

        # Split 6553 to make 256−6=250
        # Split 655 to make 256−36=220
        # Split 65 to make 256−536<0 impossible.

        def checkValid(target, number):
            # now go through all possible combination of indices to make them equals to the number
            if number == target:
                return True
            
            if target < 0 or number < target:
                return False
            
            return checkValid(target - number % 10, number // 10) or checkValid(target - number % 100, number // 100) or checkValid(target - number % 1000, number // 1000)



        result = 0
        for i in range(1, n+1):
            if checkValid(i, i*i):
                result += (i*i)
        
        return result
111