Matchsticks to Square

Explanation & Solution

Description

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.

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

Output: true

Explanation: The total length is 8, so each side must be 2. We can form four sides: [2], [2], [2], [1,1].

Constraints

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10^8

Approach

Backtracking pattern

1. Check if a Square is Possible

Calculate the total length of all matchsticks
If the total is not divisible by 4, it is impossible to form a square — return false
Compute the target side length: side = total / 4

2. Sort Matchsticks in Descending Order

Sort the matchsticks from largest to smallest
This provides early pruning: larger sticks are harder to place, so trying them first fails faster on invalid configurations
If the largest stick exceeds the target side length, return false immediately

3. Backtrack by Assigning Each Matchstick to a Side

Maintain an array sides of length 4, tracking the current length of each side
For each matchstick (by index), try placing it on each of the 4 sides
Only place it if doing so does not exceed the target side length

4. Prune Duplicate States

Use a Set called seen to track side lengths already tried at the current index
If two sides have the same current length, placing the matchstick on either would lead to equivalent states
Skipping duplicates dramatically reduces the search space

5. Check Completion

When all matchsticks have been assigned (index === matchsticks.length), verify that the first three sides equal the target
The fourth side is guaranteed correct if the others are, since the total is fixed

🧠 Key Insight

The key technique is backtracking with symmetry pruning: by sorting descending and skipping duplicate side lengths, we avoid exploring equivalent configurations

Time

O(4^n) in the worst case, but pruning makes it much faster in practice

Space

O(n) for the recursion stack

Solution Code

Restore IP Addresses

Subsets