#473

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Matchsticks to Square

The problem asks to determine if we can use matchsticks to form a square, exploring dynamic programming and backtracking.

array dynamic programming backtracking bit manipulation bitmask

Problem Statement

You are given an array of integers, where each value represents the length of a matchstick. The goal is to use all the matchsticks to form a square. No matchstick can be broken, but they can be joined together to form the sides of a square.

Return true if it is possible to arrange all the matchsticks to form a square, otherwise return false.

Examples

Example 1

Input: matchsticks = [1,1,2,2,2]

Output: true

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

You cannot find a way to form a square with all the matchsticks.

Constraints

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

Solution Approach

State Transition Dynamic Programming

This problem can be approached using state transition dynamic programming. The key is to represent the state as a bitmask, where each bit corresponds to whether a matchstick is used. This allows efficient transition between states when trying to build the square's sides.

Backtracking with Pruning

The backtracking approach tries to place each matchstick on one of the four sides of the square. Pruning is used to cut off search paths when it's impossible to complete a square, improving performance by reducing the number of recursive calls.

Bitmask Optimization

By using bitmasking to represent subsets of matchsticks, we can optimize the backtracking search. This technique reduces the complexity by enabling faster checks and transitions, especially when the number of matchsticks is large.

Complexity Analysis

Metric	Value
Time	O(N \times 2^N)
Space	O(N + 2^N)

The time complexity is O(N × 2^N), where N is the number of matchsticks, as we check all possible subsets of matchsticks. The space complexity is O(N + 2^N) due to the storage of bitmask states and the recursive calls.

What Interviewers Usually Probe

Ability to identify the state transition dynamic programming approach.
Skill in applying backtracking and pruning to reduce search space.
Familiarity with bitmasking for optimizing combinatorial problems.

Common Pitfalls or Variants

Common pitfalls

Not considering the pruning step, leading to unnecessary recursion.
Misunderstanding the problem as needing to partition into 3 parts instead of 4.
Inefficient state representation, which can result in slow performance for larger inputs.

Follow-up variants

What if the matchsticks had to form a rectangle instead of a square?
How would the problem change if we were given a fixed perimeter for the square?
What if we needed to divide the matchsticks into multiple squares instead of just one?

FAQ

What is the primary approach to solve the Matchsticks to Square problem?

The primary approach is state transition dynamic programming, which efficiently handles the combinatorial nature of the problem using bitmasking.

How does pruning help with backtracking in this problem?

Pruning eliminates paths where forming a square is impossible, reducing the number of recursive calls and speeding up the process.

What is the time complexity of the solution?

The time complexity is O(N × 2^N), where N is the number of matchsticks.

How can bitmasking optimize the solution?

Bitmasking allows efficient representation and checking of subsets of matchsticks, speeding up state transitions during the backtracking process.

What is the key to solving the problem efficiently?

The key is using dynamic programming with bitmasking to reduce the complexity of tracking which matchsticks are used and where to place them.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        def dfs(u):
            if u == len(matchsticks):
                return True
            for i in range(4):
                if i > 0 and edges[i - 1] == edges[i]:
                    continue
                edges[i] += matchsticks[u]
                if edges[i] <= x and dfs(u + 1):
                    return True
                edges[i] -= matchsticks[u]
            return False

        x, mod = divmod(sum(matchsticks), 4)
        if mod or x < max(matchsticks):
            return False
        edges = [0] * 4
        matchsticks.sort(reverse=True)
        return dfs(0)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        def dfs(u):
            if u == len(matchsticks):
                return True
            for i in range(4):
                if i > 0 and edges[i - 1] == edges[i]:
                    continue
                edges[i] += matchsticks[u]
                if edges[i] <= x and dfs(u + 1):
                    return True
                edges[i] -= matchsticks[u]
            return False

        x, mod = divmod(sum(matchsticks), 4)
        if mod or x < max(matchsticks):
            return False
        edges = [0] * 4
        matchsticks.sort(reverse=True)
        return dfs(0)

Continue Practicing

#526 beautiful arrangement #638 shopping offers #691 stickers to spell word