algoadvance

Leetcode 473. Matchsticks to Square

Problem Statement

You are given an integer array matchsticks where matchsticks[i] is the length of the i-th matchstick. You want to use all the matchsticks to form a 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.

Examples

  1. Example 1:
    • Input: matchsticks = [1,1,2,2,2]
    • Output: true
    • Explanation: You can form a square with sides of length 2: [1,1],[1,1],[2],[2],[2].
  2. Example 2:
    • Input: matchsticks = [3,3,3,3,4]
    • Output: false
    • Explanation: You cannot make a square with these matchsticks.

Constraints

Clarifying Questions

  1. Are the lengths of the matchsticks guaranteed to be positive integers?
    • Yes, as indicated by the constraints (1 <= matchsticks[i]).
  2. Can we assume that the total length of all matchsticks can sum to a number that can divide by 4 evenly in some cases?
    • Yes, that’s one of the checks we must perform. If the total length of all matchsticks is not divisible by 4, we can immediately return false.
  3. What should we return if the number of matchsticks is less than 4?
    • If the input length is less than 4, we can directly return false, since a square requires 4 sides.

Strategy

  1. Initial Check:
    • Calculate the sum of all matchsticks. If it is not divisible by 4, return false.
  2. Target Side Length:
    • The side length of the square must be sum / 4.
  3. Backtracking:
    • Sort the matchsticks in descending order (to optimize the backtracking process).
    • Use a recursive backtracking method to try to form the 4 sides with length sum / 4.

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    bool makesquare(std::vector<int>& matchsticks) {
        int sum = 0;
        for (int stick : matchsticks) {
            sum += stick;
        }

        if (sum % 4 != 0) {
            return false;
        }

        int sideLength = sum / 4;
        std::sort(matchsticks.begin(), matchsticks.end(), std::greater<int>());
        std::vector<int> sides(4, 0); // Initialize 4 sides

        return dfs(matchsticks, sides, sideLength, 0);
    }

private:
    bool dfs(std::vector<int>& matchsticks, std::vector<int>& sides, int sideLength, int index) {
        if (index == matchsticks.size()) {
            return sides[0] == sideLength && sides[1] == sideLength 
                && sides[2] == sideLength && sides[3] == sideLength;
        }

        for (int i = 0; i < 4; ++i) {
            if (sides[i] + matchsticks[index] <= sideLength) {
                sides[i] += matchsticks[index];
                if (dfs(matchsticks, sides, sideLength, index + 1)) {
                    return true;
                }
                sides[i] -= matchsticks[index];
            }

            // If this side already has no matchsticks, break to avoid redundancy
            if (sides[i] == 0) break;
        }

        return false;
    }
};

Time Complexity

This solution combines initial checks with efficient backtracking to determine if the matchsticks can form a square.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI