tardy gyro
This is my Task
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².
If there are multiple solutions (and there will be), return as far as possible the result with the largest possible values:
Examples
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.
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.
Note
Neither [n] nor [1,1,1,…,1] are valid solutions. If no valid solution exists, return nil, null, Nothing, None (depending on the language) or "[]" (C) ,{} (C++), [] (Swift, Go).
The function "decompose" will take a positive integer n and return the decomposition of N = n² as:
[x1 ... xk] or
"x1 ... xk" or
Just [x1 ... xk] or
Some [x1 ... xk] or
{x1 ... xk} or
"[x1,x2, ... ,xk]"
And this is my code that times out:
def decompose(n):
def backtrack(remaining, start):
if remaining == 0:
return []
for i in range(start, 0, -1):
if i * i <= remaining:
result = backtrack(remaining - i * i, i - 1)
if result is not None:
return result + [i]
return None
return backtrack(n * n, n - 1) or None
Anyone have idea what i did wrong or can help me write a code that won't time out
hearty iron
