Matchsticks to Square

📋

Matchsticks to Square

Edge cases:

</>

IDE

def makesquare(matchsticks: List[int]) -> bool:public boolean makesquare(int[] matchsticks)bool makesquare(vector<int>& matchsticks)function makesquare(matchsticks)

def makesquare(matchsticks: List[int]) -> bool:
    # Write your solution here
    pass

class Solution {
    public boolean makesquare(int[] matchsticks) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool makesquare(vector<int>& matchsticks) {
    // Write your solution here
    return false;
}

function makesquare(matchsticks) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueNot checking if total sum of matchsticks is divisible by 4 before backtracking.✅ Add a guard clause: if sum(matchsticks) % 4 != 0: return False

Wrong: trueGreedy approach assigning largest sticks first without backtracking all possibilities.✅ Implement full backtracking with pruning instead of greedy assignment.

Wrong: trueNot pruning or checking if any stick length exceeds side length before recursion.✅ Check max(matchsticks) <= side length before starting backtracking.

Wrong: trueIncorrect handling of empty input or single-element input, returning true instead of false.✅ Return false if input is empty or length less than 4.

Wrong: TLEUsing pure brute force recursion without pruning or memoization.✅ Add pruning by sorting sticks descending and memoize states using bitmask or DP.

✓

Test Cases

Focus on handling base cases and input constraints carefully before tackling edge cases.

Watch out for common algorithmic traps like greedy assignments and missing pruning.

Optimize your solution with memoization and pruning to handle the largest inputs efficiently.

t1_01basic

Input{"matchsticks":[1,1,2,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

You can form a square with side length 2 by using matchsticks (1+1), (2), (2), (2). Total length is 8, so each side must be 2.

💡 Try to divide the total length by 4 and check if each side can be formed.

💡 Use backtracking to assign matchsticks to 4 sides ensuring each side sums to total/4.

💡 Sort matchsticks descending and prune early when a side exceeds target length.

Why it failed: Failed basic case: likely not checking total sum divisibility by 4 or incorrect backtracking logic. Fix by verifying sum % 4 == 0 and correctly backtracking with side length constraints.

✓ Correctly handles the canonical example with proper backtracking and pruning.

t1_02basic

Input{"matchsticks":[3,3,3,3,4]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Sum is 16, divisible by 4, and can form 4 sides of length 4 by using matchsticks (4), (3+1), (3+1), (3+1) or similar combinations.

💡 Check if total length is divisible by 4 before attempting backtracking.

💡 Backtracking must try all assignments; if no valid arrangement, return false.

💡 Ensure pruning when a side exceeds target length to avoid unnecessary recursion.

Why it failed: Incorrectly returns false despite valid square; likely missing backtracking all possibilities or pruning incorrectly. Fix by exploring all assignments and pruning only when side sum exceeds target.

✓ Correctly identifies valid square can be formed.

t2_01edge

Input{"matchsticks":[]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty input means no matchsticks to form a square; must return false.

💡 Consider the base case when no matchsticks are given.

💡 Check if sum is zero or if number of sticks is zero and handle accordingly.

💡 Return false immediately if input array is empty.

Why it failed: Returns true or crashes on empty input; fix by adding a check for empty input and returning false.

✓ Properly handles empty input by returning false.

t2_02edge

Input{"matchsticks":[5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Only one matchstick cannot form a square; must return false.

💡 Check if number of matchsticks is less than 4 and handle early.

💡 A single matchstick cannot form 4 equal sides.

💡 Return false if length of matchsticks < 4.

Why it failed: Returns true for single matchstick input; fix by adding early return false if less than 4 sticks.

✓ Correctly returns false for single matchstick.

t2_03edge

Input{"matchsticks":[1,1,1,2]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Sum is 5, not divisible by 4, so cannot form a square.

💡 Always check if total sum is divisible by 4 before backtracking.

💡 If sum % 4 != 0, return false immediately.

💡 Add a guard clause to return false if sum not divisible by 4.

Why it failed: Fails to check sum divisibility and returns true incorrectly; fix by adding sum % 4 check before recursion.

✓ Correctly returns false when sum not divisible by 4.

t2_04edge

Input{"matchsticks":[10,10,10,10]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Exact boundary case: 4 matchsticks all equal length form a perfect square.

💡 Check if sum divisible by 4 and all sticks equal length.

💡 Backtracking should quickly confirm all sides equal to stick length.

💡 Return true if all sticks equal and count is 4.

Why it failed: Fails exact boundary case by not handling equal sticks or incorrect side sum checks; fix by verifying sum and side length equality.

✓ Correctly handles exact boundary with equal sticks.

t3_01corner

Input{"matchsticks":[2,2,2,2,2,2,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

All matchsticks have the same length 2; can form square with sides 4 (2+2).

💡 When all sticks are equal, check if total length divisible by 4.

💡 Backtracking should handle identical elements correctly without skipping.

💡 Ensure no early pruning skips valid equal-length partitions.

Why it failed: Fails on identical sticks due to skipping duplicates or incorrect pruning; fix by not skipping identical sticks and correctly assigning each to sides.

✓ Handles identical sticks correctly forming equal sides.

t3_02corner

Input{"matchsticks":[1,1,1,1,2,2,2,2]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Sum is 12, sides are 3; must correctly assign smaller and larger sticks to form sides.

💡 Greedy approach picking largest sticks first may fail; try all combinations.

💡 Backtracking with sorting descending helps prune but must explore all options.

💡 Avoid greedy-only approach; try placing sticks in all sides recursively.

Why it failed: Fails due to greedy approach assigning largest sticks first without backtracking all options; fix by full backtracking with pruning.

✓ Correctly backtracks to find valid square despite greedy trap.

t3_03corner

Input{"matchsticks":[1,1,1,1,1,1,1,1,1,1,1,1,1,1,14]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Sum is 28, sides 7; the large 14 stick cannot fit any side, so no square possible.

💡 Check if any single stick is longer than side length and return false early.

💡 Add pruning to reject sticks that exceed side length immediately.

💡 Return false if max stick length > side length before backtracking.

Why it failed: Fails to prune large sticks exceeding side length, causing incorrect true; fix by checking max stick length <= side length before recursion.

✓ Prunes large sticks correctly and returns false.

t4_01performance

Input{"matchsticks":[1,2,3,4,5,6,7,8,9,10,1,2,3,4,5]}

Expectednull

⏱ Performance - must finish in 2000ms

n=15 matchsticks, backtracking with pruning expected to complete within 2s; brute force O(4^n) would TLE.

💡 Use pruning and sorting to reduce search space.

💡 Memoize states or use bitmask DP to optimize.

💡 Avoid brute force pure recursion to pass time limit.

Why it failed: TLE due to exponential brute force without pruning or memoization; fix by adding pruning and memoization techniques.

✓ Efficient pruning and memoization confirmed by passing performance test.

Practice

1. You are given a set of distinct positive integers and a target sum. You need to find all unique combinations where the chosen numbers sum to the target. Each number can be chosen multiple times. Which algorithmic approach best guarantees finding all valid combinations efficiently without missing any or producing duplicates?

easy

A. Greedy algorithm that picks the largest candidate repeatedly until the sum is reached or exceeded.

B. Backtracking with sorting and frequency counting to avoid duplicates and prune early when sum exceeds target.

C. Dynamic programming using a 2D table to count the number of combinations without generating them explicitly.

D. Pure brute force recursion that tries all subsets without pruning or sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires all unique combinations summing to target, allowing reuse of candidates.

2. Step 2: Evaluate algorithm suitability

   Greedy fails because it can miss combinations; pure brute force is correct but inefficient; DP counts combinations but doesn't generate them; backtracking with sorting and frequency counting avoids duplicates and prunes search space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning and frequency counting is the standard approach [OK]

Hint: Backtracking with pruning avoids duplicates and excessive search [OK]

Common Mistakes:

• Assuming greedy always works for sum problems
• Confusing counting with generating combinations

2. Examine the following buggy backtracking code for generating combinations of size k from 1 to n. Which line contains the subtle bug that causes incorrect or duplicate results?

medium

A. Line where for loop iterates from start to n + 1

B. Line where recursion starts from 1 instead of 0

C. Line where path.pop() is called after recursion

D. Line where path is appended directly to result without copying

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so all entries in result point to the same list object.

2. Step 2: Understand consequence

   All combinations in result become identical after backtracking modifies path, causing duplicates or incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of path, not the path itself [OK]

Common Mistakes:

• Forgetting to copy path before appending to result

3. The following backtracking code attempts to generate all subsets of nums. What is the subtle bug causing incorrect output?

medium

A. Using global variable without resetting between calls

B. Not copying the current subset before appending to result causes all subsets to be the same list

C. Base case missing the empty subset

D. Forgetting to pop after including an element causes subsets to accumulate extra elements

Solution

1. Step 1: Analyze base case append

   The code appends path directly without copying, so all appended references point to the same mutable list.

2. Step 2: Consequence of mutation

   As recursion unwinds and path changes, all entries in result reflect the final state of path, causing incorrect subsets.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy (path[:]) fixes the bug [OK]

Hint: Always append a copy of the current path to result [OK]

Common Mistakes:

• Forgetting to pop after append
• Misunderstanding base case inclusion

4. Suppose the problem is changed so that candidates can be reused unlimited times (unlike original no reuse). Which modification to the backtracking algorithm correctly adapts to this change?

hard

A. Change recursive call from backtrack(i + 1, ...) to backtrack(i, ...) to allow reuse of the same candidate

B. Keep backtrack(i + 1, ...) but remove duplicate skipping to allow repeated combinations

C. Add a global visited set to prevent reusing candidates in the same combination

D. Sort candidates and prune only when candidate >= target, but keep recursion unchanged

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same candidate index can be chosen multiple times in the same combination.

2. Step 2: Modify recursion call

   Changing recursive call from backtrack(i + 1, ...) to backtrack(i, ...) allows the same candidate to be reused multiple times.

3. Step 3: Keep duplicate skipping and pruning as before

   Duplicate skipping still applies to avoid repeated combinations, and pruning remains to optimize.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recurse with same index to allow reuse [OK]

Hint: Reuse means recurse with same index, not next index [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Using visited set breaks reuse logic
• Pruning incorrectly changes conditions

5. Suppose the problem is modified so that puzzles can have repeated letters and words can be counted multiple times if they match multiple subsets of the puzzle letters. Which modification to the optimal bitmask + trie approach correctly handles this variant?

hard

A. Preprocess puzzles to remove duplicates and apply the original algorithm unchanged.

B. Modify dfs to not require the puzzle's first letter to be present in the word and allow counting multiple matches per word.

C. Enumerate all subsets of puzzle letters including duplicates and sum counts from trie traversal without filtering first letter.

D. Use a multiset trie that stores counts for repeated letters and traverse all subsets including duplicates.

Solution

1. Step 1: Understand variant requirements

   Repeated letters in puzzles and multiple counting per word require handling multisets, not just sets.

2. Step 2: Modify data structure and traversal

   A multiset trie that stores counts for repeated letters and traverses all subsets including duplicates correctly counts all matches.

3. Step 3: Why other options fail

   Ignoring first letter breaks mandatory condition; removing duplicates loses information; naive enumeration is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Multiset trie handles repeated letters and multiple counts correctly [OK]

Hint: Multiset trie needed for repeated letters and multiple counts [OK]

Common Mistakes:

• Ignoring repeated letters
• Removing duplicates incorrectly
• Dropping first letter condition