Introduction
This blog will discuss the solution to the problem of Matchsticks to Square. Here we are given an array named Matchsticks[], and Matchsticks[i] is the length of the ith matchstick. We need to use all matchsticks to make one square. We should not break any matchsticks, but we may connect them, and each matchstick should only be used once.
If we can create this square, we will print Yes; otherwise, we will print No.

Some Examples
Input
N=5, matchsticks[] = {1, 1, 1, 2, 1}
Output
Yes
Explanation:
We can form a square of length one by using all the 1s.
Input
N = 6, matchsticks[] = {3, 4, 4, 1, 2, 2}
Output
Yes
Explanation:
We can form a square of length four by combining two 2s for one side, and for another side, we will use one 1 and one 3, and the remaining two sides will be two 4s.
Backtracking Approach
- We will first determine the length of each side of the square.
- Since we have to utilize all of the provided sticks, the perimeter length will equal the sum of all of the provided integers. We just return false if the total of all integers is not a multiple of four.
- Otherwise, if the total is a multiple of 4, we must verify whether we can divide the array into four sections, each of which has a sum equal to sum/4..., which is the length of each side of the square.
- We'll keep a boolean function in which we'll provide a visited array to see whether a certain element has previously been selected or not. If my current index element is not chosen, we'll call recursively, and if we follow that track and mark that index as visited, we'll get true. We shall unmark that index if that track returns false.
Code in C++
// C++ code for Matchsticks to square
#include <bits/stdc++.h>
using namespace std;
bool backtrack(vector<int> &matchsticks, vector<int> vis, int target, int sum, int i, int k)
{
// if k == 1 then we have found all the subsets
if (k == 1)
return true;
// we found one subset, now we will go to next one which is starting from sum=0
if (sum == target)
return backtrack(matchsticks, vis, target, 0, 0, k - 1);
for (int j = i; j < matchsticks.size(); j++)
{
// if we visited this index already or if sum + matchsticks[j] > target then we can't use it
if (vis[j] || sum + matchsticks[j] > target)
continue;
vis[j] = true;
if (backtrack(matchsticks, vis, target, sum + matchsticks[j], j + 1, k))
return true;
vis[j] = false;
}
return false;
}
bool makesquare(vector<int> &matchsticks)
{
vector<int> vis(matchsticks.size(), false);
int sum = 0;
for (auto x : matchsticks)
sum += x;
if (matchsticks.size() < 4 || sum % 4)
return false;
return backtrack(matchsticks, vis, sum / 4, 0, 0, 4);
}
// Driver Code
int main()
{
vector<int> matchsticks = {1, 4, 5, 5, 2, 3};
if (makesquare(matchsticks))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
Input
matchsticks[] = {1, 4, 5, 5, 2, 3}
Output
Yes
Time Complexity
The time complexity of the above algorithm is O(N*(2^N)).
At max 2^N combinations are formed during every recursive call. Therefore time complexity is O(N*(2^N)).
Space Complexity
The space complexity of the above algorithm is O(N).
For the recursive calls, the space complexity is computed by the amount of space occupied by the recursive call stacks. Here, the maximum depth of recursion is N, hence the space complexity is O(N).
Check out this problem - Count Ways To Reach The Nth Stair