Matchsticks to Square - Practice Coding Problems

Matchsticks to Square - Problem

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 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 & Output

Example 1 — Perfect Square

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

› Output: true

💡 Note: Total length is 8, so each side needs length 2. We can group as: Side 1: [2], Side 2: [2], Side 3: [2], Side 4: [1,1]. All sides have length 2.

Example 2 — Impossible Square

$ Input: matchsticks = [3,3,3,3,4]

› Output: false

💡 Note: Total length is 16, so each side needs length 4. But we have three matchsticks of length 3, and 3 < 4, so we can't form sides of length 4 with these.

Example 3 — Single Large Stick

$ Input: matchsticks = [5,5,5,5,4,4,4,4,4,4]

› Output: false

💡 Note: Total is 44, not divisible by 4. Cannot form a square when total length is not divisible by 4.

Constraints

1 ≤ matchsticks.length ≤ 15
1 ≤ matchsticks[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array of matchstick lengths

Process

Group into 4 sides with equal sums

Output

True if square possible, false otherwise

Key Takeaway

🎯 Key Insight: This is a partition problem - we need to divide matchsticks into 4 groups with equal sums

Asked in

G Google 12 f Facebook 8 M Microsoft 6

The key insight is that we need to partition matchsticks into 4 groups with equal sums (total ÷ 4). Best approach uses optimized backtracking with sorting and pruning. Time: O(4ⁿ), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(2ⁿ × n)	O(2ⁿ)	Use memoization with bitmasks to cache results of subproblems and avoid recomputation
Optimized Backtracking	O(4ⁿ)	O(n)	Enhanced backtracking with sorting and pruning techniques to avoid redundant computations
Brute Force Backtracking	O(4ⁿ)	O(n)	Try all possible ways to assign matchsticks to 4 sides using recursive backtracking

Dynamic Programming with Bitmask — Algorithm Steps

Step 1: Use bitmask to represent which matchsticks are currently used
Step 2: For each state, try to complete one side of the square
Step 3: Memoize results to avoid recomputing same subproblems
Step 4: Return true when all matchsticks are used (mask = 2^n - 1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Bitmask

Track which matchsticks are used

Memoize

Cache results for each state

Build

Complete one side at a time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct MemoNode {
    int mask;
    bool result;
    struct MemoNode* next;
};

struct MemoNode* memo[10007];
int matchsticks[20];
int target, n;

int hash_func(int mask) {
    return mask % 10007;
}

bool get_memo(int mask) {
    int h = hash_func(mask);
    struct MemoNode* node = memo[h];
    while (node) {
        if (node->mask == mask) return node->result;
        node = node->next;
    }
    return false; // Not found
}

void set_memo(int mask, bool result) {
    int h = hash_func(mask);
    struct MemoNode* node = malloc(sizeof(struct MemoNode));
    node->mask = mask;
    node->result = result;
    node->next = memo[h];
    memo[h] = node;
}

bool has_memo(int mask) {
    int h = hash_func(mask);
    struct MemoNode* node = memo[h];
    while (node) {
        if (node->mask == mask) return true;
        node = node->next;
    }
    return false;
}

bool dp(int mask, int currentSum) {
    if (has_memo(mask)) {
        return get_memo(mask);
    }
    
    if (mask == (1 << n) - 1) {
        return true;
    }
    
    if (currentSum == target) {
        bool result = dp(mask, 0);
        set_memo(mask, result);
        return result;
    }
    
    for (int i = 0; i < n; i++) {
        if (!(mask & (1 << i)) && currentSum + matchsticks[i] <= target) {
            if (dp(mask | (1 << i), currentSum + matchsticks[i])) {
                set_memo(mask, true);
                return true;
            }
        }
    }
    
    set_memo(mask, false);
    return false;
}

bool solution(int* sticks, int size) {
    memset(memo, 0, sizeof(memo));
    memcpy(matchsticks, sticks, size * sizeof(int));
    
    int total = 0;
    for (int i = 0; i < size; i++) {
        total += matchsticks[i];
    }
    if (total % 4 != 0) return false;
    
    target = total / 4;
    n = size;
    
    return dp(0, 0);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int sticks[20];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL && size < 20) {
        sticks[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(sticks, size);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n possible states in memoization table, each state processes n matchsticks

✓ Linear Growth

Space Complexity

O(2ⁿ)

Memoization table stores results for 2^n possible bitmask states

✓ Linear Space

128.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler