Table of contents
1.
Introduction
1.1.
Some Examples
2.
Backtracking Approach
2.1.
Code in C++
2.1.1.
Time Complexity
2.1.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is backtracking?
3.2.
What does the sqrt function in C++ do?
3.3.
What are the applications of recursion?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Matchsticks to Square

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

Matchsticks to Square

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

  1. We will first determine the length of each side of the square.
  2. 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.
  3. 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.
  4. 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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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 

Frequently Asked Questions

What is backtracking?

Backtracking is an algorithmic approach for recursively solving problems by trying to construct a solution one piece at a time and rejecting any ideas that fail to meet the problem's requirements at any point in time (by time, here, is referred to as the time elapsed till reaching any level of the search tree).

What does the sqrt function in C++ do?

The sqrt function in C++ calculates the square root of a number in C++ and it gives the floor value of the exact square root. For example, the square root of 8 is 2.828 but if we do sqrt(8) it will give us 2 as the answer because the ceil value of 2.8 is 2.

What are the applications of recursion?

  • The NP issue cannot be solved in general, although it can be addressed to a certain degree (not totally) using recursion by restricting recursion depth.
  • Without recursion, the most crucial data structure, 'Tree,' does not exist. We can iteratively solve this as well, but it will be a difficult effort.
  • Recursion is used in several well-known sorting algorithms (Quick sort, Merge sort, and so on).
  • Recursion is used extensively in all puzzle games (Chess, Candy Crush, and so on).

Conclusion

In this article, we discussed the problem of MatchSticks to Square. We have discussed its approach based on backtracking, and we have also discussed the time and space complexities of the approach. I hope you must have gained some insight into this problem, and now it is your turn to code this problem in your way.\
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.

We hope that this blog has helped you enhance your knowledge regarding puzzles, and if you liked this blog, check other links.

Do upvote our blog to help other ninjas grow.

Happy Coding!"


Live masterclass