{x}
blog image

Matchsticks to Square

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

 

Example 1:

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

 

Constraints:

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 108

473. Matchsticks to Square

This problem asks whether we can form a square using all the given matchsticks without breaking any of them. Each matchstick must be used exactly once.

Approach: Backtracking (Solution 1)

This approach uses backtracking to explore all possible combinations of assigning matchsticks to the four sides of the square.

Algorithm:

  1. Preprocessing:

    • Calculate the total length of all matchsticks (s).
    • Check if the total length is divisible by 4. If not, it's impossible to form a square, so return false.
    • Calculate the required side length of the square (x = s / 4).
    • Check if any single matchstick is longer than x. If so, it's impossible to form a square, so return false.
    • Sort the matchsticks in descending order. This improves the efficiency of the backtracking algorithm by trying larger matchsticks first, often leading to early pruning.

  2. Backtracking (DFS):

    • dfs(u): This recursive function explores the possibilities starting from the u-th matchstick.
    • Base Case: If u reaches the end of the matchsticks array, it means all matchsticks have been used, and a square has been formed, so return true.
    • Recursive Step: Iterate through the four sides of the square (i from 0 to 3). Try adding the current matchstick (matchsticks[u]) to each side.
      • Check for Equality: If this is not the first side, and it is equal in length to the previous side, we skip adding it. We do this to avoid redundant and inefficient checks.
      • Check Length: If the side's length (edges[i]) after adding the matchstick exceeds x, the side length constraint is violated, so continue to the next side.
      • Recursive Call: Recursively call dfs(u + 1) to continue with the next matchstick. If the recursive call returns true, it means a square can be formed, so return true.
      • Backtrack: If the recursive call returns false, it means this path doesn't lead to a solution, so remove the matchstick from the current side (edges[i] -= matchsticks[u]) and try another side.
    • If none of the sides work, return false.

Time Complexity: O(4n), where n is the number of matchsticks. In the worst case, we explore all possible ways to assign matchsticks to the four sides. However, the sorting and early pruning significantly reduce the actual runtime.

Space Complexity: O(n) due to the recursion depth in the dfs function.

Approach: Bit Manipulation and Dynamic Programming (Solution 2)

This approach uses bit manipulation to represent the states of matchsticks and dynamic programming to optimize the search.

Algorithm:

  1. Preprocessing: Similar to Solution 1, perform the same initial checks (sum, divisibility by 4, max length). Sort the matchsticks.

  2. Dynamic Programming (Memoization):

    • dfs(state, t): This function uses memoization (@cache in Python) to store the results of subproblems. state is a bitmask representing which matchsticks have been used (1 if used, 0 if not). t is the current total length of matchsticks assigned to one side of the square, modulo s.
    • Base Case: If all matchsticks have been used (state == (1 << len(matchsticks)) - 1), a solution is found, return True.
    • Recursive Step: Iterate through the matchsticks:
      • Skip if the matchstick is already used.
      • If adding the matchstick exceeds the allowed side length, break the loop.
      • Recursively call dfs with the updated state and t. If the recursive call returns true, return true.
    • If no solution is found, return false.

Time Complexity: O(n * 2n), where n is the number of matchsticks. The state space is 2n, and for each state, we iterate through n matchsticks. The memoization significantly reduces redundant computations.

Space Complexity: O(2n) due to the memoization table.

Code Examples (Python): The code examples provided in the original problem description demonstrate both approaches. The Python code for Solution 2 utilizes the @cache decorator for memoization, which is a convenient way to implement dynamic programming in Python. Other languages might require explicit memoization using dictionaries or arrays.