D
DevExCode

LeetCode 473: Matchsticks to Square Solution

Master LeetCode problem 473 (Matchsticks to Square), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use backtracking to try all possible ways of forming a square using the given matchsticks. We can track the sum of each side of the square we are forming and check if all sides are equal to the target side length (total sum of matchsticks divided by 4). We can recursively try different combinations of matchsticks for each side, and if we successfully form all four sides, we return true.

Algorithm:

  1. Calculate the total sum of all matchsticks.
  2. If the total sum is not divisible by 4, return false as it is not possible to form a square.
  3. Sort the matchsticks array in descending order to try longer matchsticks first.
  4. Create an array to store the current sum of each side of the square.
  5. Start backtracking by trying to form each side:
    • If we have formed all four sides, return true.
    • Iterate through each matchstick:
      • If adding the current matchstick to the current side sum does not exceed the target side length:
        • Mark the matchstick as used.
        • Recur for the next side.
        • If the recursion returns true, return true.
        • Unmark the matchstick and backtrack.
  6. If we have exhausted all matchsticks and could not form the square, return false.

Time Complexity:

The time complexity of this approach is O(4^N) where N is the number of matchsticks.

Space Complexity:

The space complexity is O(N) for the recursion stack and the array to track the current sum of each side.

:

Solution Code

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int stick : matchsticks) {
            sum += stick;
        }
        
        if (sum % 4 != 0) {
            return false;
        }
        
        Arrays.sort(matchsticks);
        return backtrack(matchsticks, new int[4], sum / 4, matchsticks.length - 1);
    }
    
    private boolean backtrack(int[] matchsticks, int[] sides, int target, int index) {
        if (index == -1) {
            return sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3];
        }
        
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, target, index - 1)) {
                    return true;
                }
                sides[i] -= matchsticks[index];
            }
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 473 (Matchsticks to Square)?

This page provides optimized solutions for LeetCode problem 473 (Matchsticks to Square) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 473 (Matchsticks to Square)?

The time complexity for LeetCode 473 (Matchsticks to Square) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 473 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 473 in Java, C++, or Python.

Back to LeetCode Solutions