Matchsticks to Square
Matchsticks to Square is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the N-Queens / Constraint Satisfaction subpattern.
Problem statement
You are given matchsticks, where each integer represents the length of one matchstick. Matchsticks may be arranged end to end, but they cannot be broken, and every matchstick must be used exactly once.
Determine whether the matchsticks can form a square: four sides with equal total length. Return true if such an arrangement exists, or false otherwise.
Example 1:
Input: matchsticks = [1,2,3,4,5,6,7,8] Output: true Explanation: The sticks can be grouped as (1,8), (2,7), (3,6), and (4,5), giving four sides of length 9.
Example 2:
Input: matchsticks = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,6] Output: false Explanation: The total length is 20, so each side would need length 5, but one matchstick already has length 6 and cannot fit on any side.
Example 3:
Input: matchsticks = [3,3,3,3,4,4,4,4] Output: true Explanation: Pairing one stick of length 3 with one stick of length 4 on each side produces four sides of length 7.
Constraints:
- 4 <= matchsticks.length <= 15 - 1 <= matchsticks[i] <= 10^8 - The sum of all values in matchsticks is at most 2 10^8 - Each value in matchsticks is an integer
Topics and companies
Topics: Array, Backtracking, Recursion, Sorting.
How to practise Matchsticks to Square on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(4^n) worst case, where n is matchsticks.size(), plus O(n log n) for sorting. time and O(n) for the recursion stack; the four side totals use O(1) additional space. space.
Open Matchsticks to Square in the code editor, or read the Matchsticks to Square editorial for a worked solution with its approach and complexity analysis.
Where Matchsticks to Square sits in the DSA pattern sheet
- Backtracking Patterns pattern guide
- N-Queens / Constraint Satisfaction subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Matchsticks to Square
Other problems that use the same N-Queens / Constraint Satisfaction and Backtracking Patterns techniques:
- N-Queens — Hard, same subpattern
- N-Queens II — Hard, same subpattern
- Sudoku Solver — Hard, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern