Given an integer array, matchsticks, where matchsticks[i] is the length of the $ith$ matchstick. Use every single matchstick to create a square. No stick should be broken, although they can be connected, and each matchstick can only be used once.

Return TRUE if we can make this square; otherwise, return FALSE.

Constraints:

• $1 \leq$ matchsticks.length $\leq 15$

• $1 \leq$ matchsticks[i] $\leq 10^3$

The main strategy behind solving the Matchsticks to Square problem is backtracking. First, we determine whether forming a square is possible by calculating the square's perimeter and potential side length. If a square is possible, we attempt to assign the matchsticks individually to each side, starting with the longest matchsticks. If a matchstick cannot be placed on a side, we remove it and backtrack to try the other matchsticks. After all the matchsticks have been placed, we check if a square has been formed by comparing the lengths of the four sides. If all sides are equal, a square has been formed. Otherwise, we backtrack to try other possibilities.

The key steps of the algorithm are as follows:

1. Find the perimeter of the square by summing the lengths of all the matchsticks.

2. Perform an integer division of the perimeter by $4$ to determine the possible side length of the square. This division checks if the matchsticks can be divided into four equal parts, each representing a side of the square.

   1. If the perimeter is not perfectly divisible by 4, it's impossible to form a square using all the matchsticks. In such cases, either some matchsticks will be left unused, or the sides of the square will remain incomplete.

3. Check if making a square is possible with this possible side length. You can do this by multiplying the possible side length with $4$ and comparing the result with the perimeter. If both are unequal, return FALSE.

4. Sort the matchsticks in descending order, using the longest matchsticks first. This helps reduce the number of recursive calls.

5. Initialize an array, sides, of size $4$ with zeros. This array keeps track of the current lengths of the square's four sides as matchsticks are added.

6. Recurse to try all possible options.

For the recursive part, we implement the function MatchsticksToSquareRec(), which receives index as a parameter representing the current matchstick under consideration. The recursive function works as follows:

Base case:

• Check if a square has been formed if all matchsticks have been used (i.e., index equals the total number of matchsticks).

  • To verify if a square is formed, check if all four sides are equal by comparing the $0^{th}$, $1^{st}$, $2^{nd}$ , and $3^{rd}$indexes of sides. If all are equal, return TRUE. Otherwise, return FALSE.

Recursive step:

• For each of the four sides, determine if the current matchstick (matchsticks[index]) can be added to that side without exceeding the possible side length.

  • If the matchstick can be added, update the side’s length and make a recursive call to MatchsticksToSquareRec() with the next index.

    • If this recursive call returns TRUE, return TRUE as the overall result.

    • If the call returns FALSE, backtrack by removing the matchstick from the side and attempting to place it on the next side.

  • If the matchstick cannot be added to the current side, try placing it on the next side.

• If the matchstick cannot be placed on any of the sides, return FALSE.

Let’s look at the following illustration to get a better understanding of the solution: