Find A Series of Numbers Who when Squared and Summed are equal to a given Square I am working on a CodeWars titled 'Square into Squares. Protect trees!' it can be found here: https://www.codewars.com/kata/54eb33e5bc1a25440d000891/train/javascript

I have a working solution, the issue is that the performance is so horrid that if I run it with an argument higher than around 15 my browser/tab freezes. I would like some suggestions as towards how I could create a more efficient algorithm for this kind of problem, or just improve my current algorithm to be more performant.

Codewars times out as a result of its bad performance on the full test kit for the Kata. I am entirely certain that the issue is caused by calculating the square of every number beneath my argument number, but since I'm not particularly talented at math that was my procedural way of finding the correct values. I thought if I could find a way of eliminating many of the values before calculating their square that would solve the problem, but I haven't thought of a way yet.



let sol = []

function decompose(n) {
    sol = []
    let expMap = {}
    for(let i = 1; i &lt; n; i++){
      expMap[i] = Math.pow(i, 2)
    }

    for(let prop in expMap){
      solutionFinder(prop, expMap, Math.pow(n, 2), [])
    }
    if(sol.length &gt; 0) return sol
    return null
}

const solutionFinder = (val, set, currentValue, currentSet) =&gt; {
  const dataArr = [...currentSet]
  const dataClone = {...set}

  currentValue -= dataClone[val]
  dataArr.push(val)
  delete dataClone[val]

  if(currentValue &lt; 0) return;

  if(!(currentValue === 0)){
    for(let prop in dataClone){
      solutionFinder(prop, dataClone, currentValue, dataArr)
    }
  }

  if(currentValue === 0){
    if(sol.length === 0 || arrSum(sol) &lt; arrSum(currentSet)){
      sol = dataArr.map(i =&gt; parseInt(i)).sort((a, b) =&gt; a - b)
      return
    }
  }

  return
}

const arrSum = arr =&gt; arr.reduce((a,b) =&gt; a + b, 0)




I am relatively new to programming (Started in February), and still struggle with developing algorithms with good time complexity, any advice about how to make this algorithm more efficient or an algorithm that would work better for this job would be welcome.
Optimization starts from a sound logical process

Let's think about the problem in particular.


  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 the result with the largest possible values


And later, it specifies


  If no valid solution exists, return nil, null, Nothing, None (depending on the language) or "[]" (C) ,{} (C++), [] (Swift, Go).


You were on the right track with your solution, but the code does not exemplify that. Your solution iterates through a map of all  pairings and removes one at a time per iteration of solutionFinder. At worst, this will go through every permutation of 1, ..., . And ideally, you should never reach a case where you're even looking at numbers that have larger squares than your remaining value.

So, how can we improve this? Well, as I said before, optimization starts from a sound logical process. There are 2 conditions in the specifications that can help us build that solution:


The sequence must be strictly increasing
If there are multiple solutions, we must return the result with the largest possible values


Because I'm pretty sure you're already within this same line of problem solving for the problem itself, I'll just jump to what I'm thinking:


   Start with  and .

 Iterating from j=i down to 1, subtract  from . Skip  particularly.

 If that value equals 0, return a list with just i.

 Otherwise, recursively call the same method with that value and j. Return a list of that call with j appended to it if it's nonnull, and null otherwise.

 If i=0, return null.  


This methodology guarantees the highest number solution, and doesn't iterate through all permutations. Done right, it'll output the right list or null in order.

So how does this constitute a valid code review? Well, it points out some extraneous points in your solution.

Couple miscellaneous points

There is no need to keep a map of integers to their squares. You can iterate down from the highest possible square to 1 and lower your time complexity while maintaining the uniqueness of your output.

You should build the list through return values, rather than modification within a method parameter. The beauty of recursion is the ability to use recursive method evaluations within another call of the same method.

You have 2 variables named sol in different scopes. It's hard to determine where the solution actually goes. I would recommend removing the global scoped sol, and using the above points to return the solution from solutionFinder.