Matchsticks to Square - Leetcode 473 -CSharp

// Sample input arrays

int[] invalidInput = [0, 1, 2, 2, 2];
int[] input = [1, 1, 2, 2, 2];

// Test the MakeSquare function with both inputs
Console.WriteLine(MakeSquare(invalidInput) ? "Has solution" : "No solution");
Console.WriteLine(MakeSquare(input) ? "Has solution" : "No solution");
return;

static bool MakeSquare(int[] matchSticks) // root function that checks if matchsticks can form a square
{
    const int sideCount = 4;
    // Calculate target length that each side should have (total length / 4 sides)
    int targetLength = matchSticks.Sum() / 4;
    // Array to track length of each side as we build the square
    int[] sides = new int[4];

    // Check if total length can be evenly divided into 4 equal sides
    if (Math.Abs(matchSticks.Sum() / sideCount - targetLength) > 0)
    {
        return false;
    }

    // Sort matchsticks in descending order to optimize backtracking
    // Larger matchsticks are harder to place, so try them first
    Array.Sort(matchSticks, (a, b) => b.CompareTo(a));

    return Backtrack(0);

    // Recursive backtracking function to try different matchstick placements
    bool Backtrack(int matchStickIndex)
    {
        // Base case: if all matchsticks have been placed successfully
        if (matchStickIndex == matchSticks.Length)
        {
            return true;
        }

        // Try placing current matchstick on each side
        for (int sideIdx = 0; sideIdx < 4; sideIdx++)
        {
            // Check if adding current matchstick would not exceed target length
            if (sides[sideIdx] + matchSticks[matchStickIndex] <= targetLength)
            {
                // Place matchstick on current side
                sides[sideIdx] += matchSticks[matchStickIndex];
                // Recursively try to place remaining matchsticks
                if (Backtrack(matchStickIndex + 1))
                {
                    return true;
                }

                // Backtrack by removing matchstick if solution not found
                sides[sideIdx] -= matchSticks[matchStickIndex];
            }
        }

        // No valid solution found for current matchstick
        return false;
    }
}

// Matchsticks to Square - Leetcode 473 - Python
// https://www.youtube.com/watch?v=hUe0cUKV-YY&t=354s