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 an array of integers and need to find the number of subsets whose bitwise OR equals the maximum possible OR value among all subsets. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting elements with highest bits set first

B. Iterative bitmask enumeration generating all subsets and computing their OR

C. Dynamic programming based on subset sums

D. Sorting the array and using two pointers to find max OR subsets

Solution

1. Step 1: Understand the problem requires checking all subsets

   Since the maximum bitwise OR depends on any combination of elements, all subsets must be considered.

2. Step 2: Identify approach that enumerates all subsets efficiently

   Iterative bitmask enumeration systematically generates all subsets and computes their OR, ensuring no subset is missed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets -> optimal [OK]

Hint: Bitmask enumeration covers all subsets exhaustively [OK]

Common Mistakes:

• Assuming greedy selection suffices for max OR
• Confusing subset sum DP with bitwise OR problem

2. Consider the following Python code for finding the largest divisible subset. What is the final returned list when the input is [1, 2, 3]?

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []
    nums.sort()
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[i] % nums[j] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

print(largestDivisibleSubset([1, 2, 3]))

easy

A. [1, 2]

B. [1, 3]

C. [1, 2, 3]

D. [2, 3]

Solution

1. Step 1: Trace dp and prev arrays

   Sorted nums = [1, 2, 3]. For i=1 (2), dp[1]=2, prev[1]=0 since 2 % 1 == 0. For i=2 (3), dp[2]=2, prev[2]=0 since 3 % 1 == 0 but 3 % 2 != 0 (break early).

2. Step 2: Reconstruct subset from max_index=1 or 2

   dp[1] and dp[2] both 2, max_index updated to 2 last. Reconstruct: nums[2]=3, prev[2]=0 -> nums[0]=1. Result reversed is [1, 3].

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Subset [1,3] is largest divisible subset returned [OK]

Hint: Trace dp and prev arrays carefully [OK]

Common Mistakes:

• Assuming [1,2,3] all divisible chain without checking divisibility
• Confusing indices when reconstructing subset
• Ignoring early break in inner loop

3. Consider the following Python code implementing letter case permutation using backtracking with in-place modification. What is the final output when the input string is "a1b"?

from typing import List

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]  # revert to original
    backtrack(0)
    return res

print(letterCasePermutation("a1b"))

easy

A. ['a1b', 'a1B', 'A1B', 'A1b']

B. ['a1b', 'A1b', 'a1B', 'A1B']

C. ['a1b', 'a1B', 'A1b', 'A1B']

D. ['A1b', 'a1b', 'A1B', 'a1B']

Solution

1. Step 1: Trace backtrack calls for input "a1b"

   Index 0 is 'a' (letter), toggled to 'a' then 'A'. Index 1 is '1' (digit), skipped. Index 2 is 'b' (letter), toggled to 'b' then 'B'.

2. Step 2: Collect permutations in order

   Order of appending: 'a1b', 'a1B', 'A1b', 'A1B'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected toggling order [OK]

Hint: Digits skip toggling; letters toggle lower then upper [OK]

Common Mistakes:

• Swapping order of uppercase/lowercase calls
• Misplacing digit handling

4. 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

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