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 code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]?

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Enumerate all non-empty subsets and their OR

   Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

2. Step 2: Identify max OR and count subsets with that OR

   Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted 5 subsets with max OR 3 -> matches 5 [OK]

Hint: Count subsets with OR equal to max OR -> 5 [OK]

Common Mistakes:

• Counting empty subset as valid
• Miscounting subsets with max OR

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. What is the time complexity of the optimal bitmask + trie solution for the Number of Valid Words for Each Puzzle problem, given W words with average length L, and P puzzles?

medium

A. O(W * L + P * M), where M is the average number of trie nodes traversed per puzzle

B. O(W * P * L), since each word is checked against each puzzle

C. O(W * 2^7 + P * 7), enumerating all subsets of puzzle letters for each puzzle

D. O(W * L * 26 + P * 26), traversing trie nodes for all letters

Solution

1. Step 1: Analyze word insertion

   Each word is converted to a bitmask and inserted into trie in O(L) time, total O(W * L).

2. Step 2: Analyze puzzle queries

   For each puzzle, dfs traverses trie nodes corresponding to subsets of puzzle letters, average M nodes, total O(P * M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known optimal complexity [OK]

Hint: Trie traversal depends on subsets of puzzle letters, not all words [OK]

Common Mistakes:

• Assuming brute force complexity
• Confusing 2^7 subsets with trie traversal nodes
• Ignoring average trie traversal cost

4. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes