Decomposing squared integer input to sum of squared integers less than input?

Question

I have a question as follows:

Given a positive integral number n, return a strictly increasing sequence (list/array/string depending on the language) of numbers, so that the sum of the squares is equal to n².

decompose(11) must return [1,2,4,10]. Note that there are actually two ways to decompose 11², 11² = 121 = 1 + 4 + 16 + 100 = 1² + 2² + 4² + 10² but don't return [2,6,9], since 9 is smaller than 10 (if multiple sequence of squared integers can be used, go with the greatest one - so 10 instead of 9 in the above case).

For decompose(50) don't return [1, 1, 4, 9, 49] but [1, 3, 5, 8, 49] since [1, 1, 4, 9, 49] doesn't form a strictly increasing sequence.

I have gotten nowhere, trying this (which probably is poorly done):

function sq2squares($n) {

     $starting = ($n - 1) ** 2;
     $square = $n**2;
     $range = range(1, $n -1);
     $start = $square - $starting;

     foreach($range as $r => $v) {
          if($v**2 > $start) {
               unset($range[$r]);
          }
     }

    # $range here is [1, 2, 3, 4, 5, 6, 7, 8, 9];
    
    foreach(array_reverse($range) as $r) {
        if($r**2 < $start) {
            $start -= $r**2;
        }
    }

    print_r($results); // [49] || Should be: [1,3,5,8,49] 

}

I have subtracted square of input from largest next number (49) which leaves 99. Then I want to iterate over the remaining integers in $range (9-1) and subtract each but ONLY if the resulting subtraction results in $start being 0. That last part is what I can't figure out.

How to iterate over the array $range and only array_push() values which result in $start being 0? Thanks.

user_4964822 · Answer

We first create an array say $dp and fill all values with -1.
Value -1 means that there is no way to form sum of squared numbers for that particular number in iteration.
Initialize $dp[1] = 1 as base case.
We iterate from 2 to $value where $value is the squared form.(121 for value 11).
For every $i in the below code, we move from square root of $i till 1 looking for square sum solutions.
If $dp[$i - $j * $j] != -1 exists, it means that a previous problem, i.e, $i - $j * $j was solved, meaning, we could express it as sum of squared numbers and $dp[$i - $j * $j] < $j represents a check that we are looking for an strictly increasing sequence with bigger number with respect to previous subproblems. If both are true, assign $dp[$i] = $j.
At the last, we need to collect values. We simply jump to previous subproblems and add value at current subproblem to result.

Snippet:

= 1; --$j){
            if($dp[$i - $j * $j] != -1 && $dp[$i - $j * $j] < $j){ // meaning can be represented as sum of squares
                $dp[$i] = $j;
                break; // since we are looking for sequence with greater numbers
            }
        }
    }
    
    $result = [];
    $curr = $value;
    // just collect all values
    while($dp[$curr] != -1){
        $result[] = $dp[$curr];
        $curr -= $dp[$curr] * $dp[$curr];
    }
    
    return $result;
}

Demo: https://3v4l.org/DEH9f

Decomposing squared integer input to sum of squared integers less than input?

1 Answers