Matchsticks to Square

▶

Steps

setup

Calculate total length and check divisibility

The algorithm sums all matchsticks and checks if the total length is divisible by 4. If not, it returns false immediately.

💡 This step quickly eliminates impossible cases, saving computation time.

Line:

total = sum(matchsticks)
if total % 4 != 0:
    return False

💡 If total length is not divisible by 4, forming a square is impossible.

setup

Sort matchsticks descending

The matchsticks are sorted in descending order to try larger sticks first, which helps prune invalid paths earlier.

💡 Sorting helps the algorithm fail faster when a large stick cannot fit, improving efficiency.

Line:

matchsticks.sort(reverse=True)

💡 Trying larger sticks first reduces unnecessary deeper recursion.

traverse

Start backtracking with empty usage

The backtracking function is called with no matchsticks used, current side sum 0, and 0 sides formed.

💡 This is the root of the recursion tree where the algorithm begins exploring combinations.

Line:

return backtrack(0, 0, 0)

💡 We start with an empty square and try to build sides step by step.

traverse

Try adding matchstick 0 (length 2) to side 0

Matchstick 0 is unused, adding it to current side sum 0 results in sum 2, which is <= side length 3, so recurse with updated mask and sum.

💡 Trying the first unused matchstick to build the current side incrementally.

Line:

if not (used_mask & (1 << i)):
    next_sum = curr_sum + matchsticks[i]
    if next_sum <= side:

💡 We explore the path where matchstick 0 is part of the first side.

traverse

Try adding matchstick 1 (length 2) to side 0

Matchstick 1 is unused, adding it to current sum 2 results in 4, which exceeds side length 3, so skip this matchstick.

💡 We prune paths where the side length would be exceeded.

Line:

if next_sum <= side:

💡 Pruning invalid paths early avoids unnecessary recursion.

traverse

Try adding matchstick 2 (length 2) to side 0

Matchstick 2 is unused, adding it to current sum 2 results in 4, which exceeds side length 3, so skip this matchstick.

💡 Again pruning paths that exceed side length.

Line:

if next_sum <= side:

💡 Repeated pruning shows how sorting helps avoid futile branches.

traverse

Try adding matchstick 3 (length 1) to side 0

Matchstick 3 is unused, adding it to current sum 2 results in 3, which equals side length, so recurse with next side.

💡 Completing a side triggers recursion to build the next side from sum 0.

Line:

if next_sum == side:
    if backtrack(next_mask, 0, sides_formed + 1):

💡 Completing sides resets current sum and increments sides formed.

traverse

Try adding matchstick 1 (length 2) to side 1

Matchstick 1 is unused, adding it to current sum 0 results in 2, which is <= side length, recurse with updated mask and sum.

💡 Building the second side similarly by adding unused sticks.

Line:

if not (used_mask & (1 << i)):
    next_sum = curr_sum + matchsticks[i]
    if next_sum <= side:

💡 The algorithm tries to build each side independently but tracks used sticks globally.

traverse

Try adding matchstick 2 (length 2) to side 1

Matchstick 2 is unused, adding it to current sum 2 results in 4, exceeding side length, so skip.

💡 Pruning invalid paths continues at deeper recursion levels.

Line:

if next_sum <= side:

💡 Pruning prevents exploring impossible combinations.

traverse

Try adding matchstick 4 (length 1) to side 1

Matchstick 4 is unused, adding it to current sum 2 results in 3, which equals side length, so recurse with next side.

💡 Completing the second side and moving to build the third side.

Line:

if next_sum == side:
    if backtrack(next_mask, 0, sides_formed + 1):

💡 The algorithm successfully completes sides and moves forward.

traverse

Try adding matchstick 2 (length 2) to side 2

Matchstick 2 is unused, adding it to current sum 0 results in 2, which is <= side length, recurse with updated mask and sum.

💡 Building the third side with the last unused matchstick.

Line:

if not (used_mask & (1 << i)):
    next_sum = curr_sum + matchsticks[i]
    if next_sum <= side:

💡 The last side is being formed with the remaining matchstick.

compare

All matchsticks used and three sides formed

Since three sides are formed, the algorithm returns true, as the fourth side is implicitly complete.

💡 The base case confirms a valid square formation.

Line:

if sides_formed == 3:
    return True

💡 Completing three sides guarantees the fourth side matches automatically.

backtracking

Memoize and return true up the call stack

Each recursive call memoizes the true result for its state and returns true to its caller, propagating success.

💡 Memoization prevents re-exploring the same states in future calls.

Line:

memo[(used_mask, curr_sum, sides_formed)] = True
return True

💡 Memoization caches successful states to optimize future calls.

reconstruct

Final result returned: true

The makesquare function returns true, indicating the matchsticks can form a square.

💡 The final output confirms the problem is solvable with the given input.

Line:

return backtrack(0, 0, 0)

💡 The algorithm successfully found a valid combination of matchsticks.

from typing import List

def makesquare(matchsticks: List[int]) -> bool:
    total = sum(matchsticks)  # STEP 1
    if total % 4 != 0:  # STEP 1
        return False
    side = total // 4
    matchsticks.sort(reverse=True)  # STEP 2
    n = len(matchsticks)
    memo = {}

    def backtrack(used_mask, curr_sum, sides_formed):
        if sides_formed == 3:  # STEP 12
            return True
        if (used_mask, curr_sum, sides_formed) in memo:
            return memo[(used_mask, curr_sum, sides_formed)]
        for i in range(n):  # STEP 3-11
            if not (used_mask & (1 << i)):
                next_sum = curr_sum + matchsticks[i]
                if next_sum <= side:
                    next_mask = used_mask | (1 << i)
                    if next_sum == side:
                        if backtrack(next_mask, 0, sides_formed + 1):  # STEP 7,10
                            memo[(used_mask, curr_sum, sides_formed)] = True  # STEP 13
                            return True
                    else:
                        if backtrack(next_mask, next_sum, sides_formed):  # STEP 4,8,11
                            memo[(used_mask, curr_sum, sides_formed)] = True  # STEP 13
                            return True
        memo[(used_mask, curr_sum, sides_formed)] = False
        return False

    return backtrack(0, 0, 0)  # STEP 3,14

📊

Matchsticks to Square - Watch the Algorithm Execute, Step by Step

Watching each recursive call and decision helps you understand how the algorithm explores combinations efficiently and prunes impossible paths early.

enteringmatchsticks=[1,1,2,2,2]

Call Path (current → root)

makesquare([1,1,2,2,2])

enteringmatchsticks=[2,2,2,1,1]

Call Path (current → root)

makesquare([2,2,2,1,1])

enteringused_mask=0curr_sum=0sides_formed=0

Call Path (current → root)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Remaining

i=0i=1i=2i=3i=4

enteringused_mask=1curr_sum=2sides_formed=0

Call Path (current → root)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Remaining

i=1i=2i=3i=4

Partial: [0]

choosingused_mask=1curr_sum=2sides_formed=0

Call Path (current → root)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Tried

i=1 (skipped)

Remaining

i=2i=3i=4

Partial: [0]

✂ next_sum 4 > side 3

choosingused_mask=1curr_sum=2sides_formed=0

Call Path (current → root)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Tried

i=1 (skipped)i=2 (skipped)

Remaining

i=3i=4

Partial: [0]

✂ next_sum 4 > side 3

enteringused_mask=11curr_sum=0sides_formed=1

Call Path (current → root)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Remaining

i=1i=2i=4

Partial: [0, 3]

enteringused_mask=19curr_sum=2sides_formed=1

Call Path (current → root)

backtrack(used_mask=19, curr_sum=2, sides_formed=1)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Remaining

i=2i=4

Partial: [0, 3, 1]

choosingused_mask=19curr_sum=2sides_formed=1

Call Path (current → root)

backtrack(used_mask=19, curr_sum=2, sides_formed=1)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Tried

i=2 (skipped)

Remaining

i=4

Partial: [0, 3, 1]

✂ next_sum 4 > side 3

enteringused_mask=27curr_sum=0sides_formed=2

Call Path (current → root)

backtrack(used_mask=27, curr_sum=0, sides_formed=2)

backtrack(used_mask=19, curr_sum=2, sides_formed=1)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Remaining

i=2

Partial: [0, 3, 1, 4]

enteringused_mask=31curr_sum=2sides_formed=2

Call Path (current → root)

backtrack(used_mask=31, curr_sum=2, sides_formed=2)

backtrack(used_mask=27, curr_sum=0, sides_formed=2)

backtrack(used_mask=19, curr_sum=2, sides_formed=1)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Partial: [0, 3, 1, 4, 2]

backtrackingused_mask=31curr_sum=2sides_formed=3

Call Path (current → root)

backtrack(used_mask=31, curr_sum=2, sides_formed=3)

backtrack(used_mask=27, curr_sum=0, sides_formed=2)

backtrack(used_mask=19, curr_sum=2, sides_formed=1)

backtrack(used_mask=11, curr_sum=0, sides_formed=1)

backtrack(used_mask=1, curr_sum=2, sides_formed=0)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Partial: [0, 3, 1, 4, 2]

Found 1: [true]

backtrackingused_mask=0curr_sum=0sides_formed=0

Call Path (current → root)

backtrack(used_mask=0, curr_sum=0, sides_formed=0)

Tried

i=0i=3i=1i=4i=2

Found 1: [true]

backtrackingmatchsticks=[2,2,2,1,1]

Call Path (current → root)

makesquare([2,2,2,1,1])

Found 1: [true]

Key Takeaways

✓ Backtracking with bitmasking efficiently tracks used matchsticks and avoids revisiting states.

This insight is hard to see from code alone because bitmask operations and memoization states are abstract without visualization.

✓ Sorting matchsticks in descending order helps prune impossible paths early, reducing recursion depth.

Seeing pruning in action clarifies why sorting is a critical optimization.

✓ Completing three sides guarantees the fourth side is complete, simplifying the base case.

Understanding this base case is easier when watching the recursion tree reach the leaf node.

Practice

1. Consider the following Python code implementing the optimal backtracking solution for Combination Sum III. What is the final value of res after calling combinationSum3(3, 7)?

easy

A. [[1, 2, 4]]

B. [[1, 3, 3]]

C. [[2, 2, 3]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls for k=3, n=7

   Start from 1, try combinations of size 3 summing to 7. Valid combos are [1,2,4] only because 1+2+4=7.

2. Step 2: Verify no other combos meet criteria

   Other combos like [1,3,3] or [2,2,3] are invalid due to duplicates or sum mismatch.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only [1,2,4] sums to 7 with 3 distinct numbers [OK]

Hint: Only distinct numbers summing to 7 with size 3 is [1,2,4] [OK]

Common Mistakes:

• Including duplicates like [1,3,3]
• Miscounting sum or size

2. Consider the following Python code implementing combination sum with reuse allowed:

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)
    backtrack(0, [], target)
    return result

print(combinationSum([2,3,6,7], 7))

What is the exact output of this code?

easy

A. [[7]]

B. [[2, 2, 3], [7]]

C. [[2, 2, 3]]

D. [[7], [2, 2, 3]]

Solution

1. Step 1: Trace backtrack calls for candidates=[2,3,6,7], target=7

   Sorted candidates: [2,3,6,7]. The function tries counts of 2 from 0 to 3 (max_use=3), then recurses on next index. Valid combinations found are [7] and [2,2,3].

2. Step 2: Check order of results appended

   Backtracking explores index 0 with counts 0..3, then index 1, so [7] is found after [2,2,3]. The result list appends [7] first, then [2,2,3]. But since the code appends when target==0, the order is [[7], [2, 2, 3]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected combinations with correct order [OK]

Hint: Order depends on recursion path, not sorted output [OK]

Common Mistakes:

• Assuming output is sorted by combination length or lex order
• Missing one valid combination

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

4. You are given a list of words and a list of puzzles, each puzzle being a string of 7 unique letters. For each puzzle, you need to count how many words satisfy two conditions: the word contains the puzzle's first letter, and all letters of the word are contained within the puzzle. Which approach guarantees an optimal solution for this problem?

easy

A. Use bitmasking to represent words and puzzles, combined with a trie to efficiently count valid words for each puzzle.

B. Use a brute force approach checking each word against each puzzle with set containment checks.

C. Use a dynamic programming approach to count subsets of puzzle letters matching words.

D. Use a greedy approach selecting words that share the most letters with puzzles.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking subsets of puzzle letters and matching words efficiently, which is expensive with brute force.

2. Step 2: Identify optimal approach

   Bitmasking encodes letters as bits, and a trie built on word bitmasks allows fast traversal of valid subsets, ensuring efficient counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + trie approach is known optimal for this problem [OK]

Hint: Bitmask + trie efficiently enumerates subsets [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP without bitmasking
• Greedy approaches fail on subset constraints

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