Matchsticks to Square

🎯

Matchsticks to Square

mediumBACKTRACKINGAmazonGoogleFacebook

Imagine you have a bunch of matchsticks and want to form a perfect square by using all of them without breaking any. Can you figure out if it's possible?

💡 This problem is a classic backtracking challenge where you try to partition a set into equal subsets. Beginners often struggle because it requires careful pruning and understanding how to explore combinations efficiently.

📋

Problem Statement

Given an array of integers representing the lengths of matchsticks, determine if you can use all the matchsticks to form a square. You cannot break any matchstick, but you can link them up, and each matchstick must be used exactly once. Return true if you can form such a square, otherwise false.

1 ≤ number of matchsticks ≤ 151 ≤ length of each matchstick ≤ 10^8

💡

Example

Input"[1,1,2,2,2]"

Outputtrue

You can form a square with side length 3 by using matchsticks (1+2), (1+2), (2), (2).

Input"[3,3,3,3,4]"

Outputfalse

It's impossible to form a square with all matchsticks.

• All matchsticks have the same length → should return true
• Only 1 matchstick → should return false
• Sum of lengths not divisible by 4 → should return false
• Large lengths but few matchsticks → test performance and correctness

⚠️

Common Mistakes

Not checking if total length is divisible by 4

Wastes time exploring impossible solutions

✅ Add early check for divisibility by 4

Not sorting matchsticks before backtracking

Backtracking explores many unnecessary branches

✅ Sort matchsticks descending to prune early

Not pruning when a side is empty and fails

Repeatedly tries equivalent empty sides, wasting time

✅ Break loop when side is empty and placement fails

Forgetting to backtrack (undo assignments)

Incorrect results or infinite recursion

✅ Always remove matchstick from side after recursive call

Not memoizing states in bitmask approach

Repeatedly recomputes same states, causing TLE

✅ Use memo dictionary keyed by bitmask and current sums

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's search space and why naive attempts are inefficient, laying the foundation for pruning and optimization.

Intuition

Try every possible way to assign matchsticks to four sides and check if all sides end up equal.

Algorithm

1. Calculate the total length and check if divisible by 4.
2. Use recursion to try placing each matchstick in one of the four sides.
3. If at any point a side exceeds the target length, backtrack.
4. If all matchsticks are placed and all sides equal target, return true.

💡 The challenge is to systematically try all assignments and backtrack when invalid, which is conceptually simple but computationally expensive.

</>

Code

from typing import List

def makesquare(matchsticks: List[int]) -> bool:
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    side = total // 4
    sides = [0] * 4

    def backtrack(index):
        if index == len(matchsticks):
            return all(s == side for s in sides)
        for i in range(4):
            if sides[i] + matchsticks[index] <= side:
                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]
        return False

    return backtrack(0)

# Driver code
if __name__ == '__main__':
    print(makesquare([1,1,2,2,2]))  # True
    print(makesquare([3,3,3,3,4]))  # False

Line Notes

total = sum(matchsticks)Calculate total length to determine feasibility

if total % 4 != 0:If total not divisible by 4, square formation impossible

def backtrack(index):Recursive function to try placing matchsticks starting from index

for i in range(4):Try placing current matchstick in each of the 4 sides

if sides[i] + matchsticks[index] <= side:Only place if it doesn't exceed target side length

sides[i] += matchsticks[index]Choose this side for current matchstick

if backtrack(index + 1):Recurse to next matchstick; if success, propagate True

sides[i] -= matchsticks[index]Backtrack: remove matchstick from side

import java.util.*;

public class MatchsticksToSquare {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = total / 4;
        int[] sides = new int[4];
        return backtrack(matchsticks, sides, 0, side);
    }

    private boolean backtrack(int[] matchsticks, int[] sides, int index, int side) {
        if (index == matchsticks.length) {
            for (int s : sides) if (s != side) return false;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, index + 1, side)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }

    public static void main(String[] args) {
        MatchsticksToSquare solver = new MatchsticksToSquare();
        System.out.println(solver.makesquare(new int[]{1,1,2,2,2})); // true
        System.out.println(solver.makesquare(new int[]{3,3,3,3,4})); // false
    }
}

Line Notes

for (int m : matchsticks) total += m;Sum all matchsticks to check divisibility

if (total % 4 != 0) return false;Quick check to avoid unnecessary recursion

private boolean backtrack(...)Recursive helper to assign matchsticks to sides

for (int i = 0; i < 4; i++) {Try each side for current matchstick

if (sides[i] + matchsticks[index] <= side) {Only proceed if side length not exceeded

sides[i] += matchsticks[index];Add matchstick length to side

if (backtrack(...)) return true;If successful assignment found, return true

sides[i] -= matchsticks[index];Backtrack by removing matchstick from side

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = total / 4;
        vector<int> sides(4, 0);
        return backtrack(matchsticks, sides, 0, side);
    }

private:
    bool backtrack(vector<int>& matchsticks, vector<int>& sides, int index, int side) {
        if (index == matchsticks.size()) {
            for (int s : sides) if (s != side) return false;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, index + 1, side)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {1,1,2,2,2};
    vector<int> test2 = {3,3,3,3,4};
    cout << boolalpha << sol.makesquare(test1) << "\n"; // true
    cout << boolalpha << sol.makesquare(test2) << "\n"; // false
    return 0;
}

Line Notes

for (int m : matchsticks) total += m;Sum all matchsticks to check feasibility

if (total % 4 != 0) return false;If total length not divisible by 4, no solution

bool backtrack(...)Recursive function to assign matchsticks to sides

for (int i = 0; i < 4; i++) {Try placing current matchstick in each side

if (sides[i] + matchsticks[index] <= side) {Only place if side length limit not exceeded

sides[i] += matchsticks[index];Add matchstick length to side

if (backtrack(...)) return true;If successful, propagate true

sides[i] -= matchsticks[index];Backtrack by removing matchstick

function makesquare(matchsticks) {
    const total = matchsticks.reduce((a,b) => a+b, 0);
    if (total % 4 !== 0) return false;
    const side = total / 4;
    const sides = [0,0,0,0];

    function backtrack(index) {
        if (index === matchsticks.length) {
            return sides.every(s => s === side);
        }
        for (let i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(index + 1)) return true;
                sides[i] -= matchsticks[index];
            }
        }
        return false;
    }

    return backtrack(0);
}

// Test cases
console.log(makesquare([1,1,2,2,2])); // true
console.log(makesquare([3,3,3,3,4])); // false

Line Notes

const total = matchsticks.reduce((a,b) => a+b, 0);Sum all matchsticks to check divisibility

if (total % 4 !== 0) return false;Quick check to avoid unnecessary recursion

function backtrack(index) {Recursive function to assign matchsticks starting at index

for (let i = 0; i < 4; i++) {Try placing current matchstick in each side

if (sides[i] + matchsticks[index] <= side) {Only place if side length not exceeded

sides[i] += matchsticks[index];Add matchstick length to side

if (backtrack(index + 1)) return true;If successful assignment found, return true

sides[i] -= matchsticks[index];Backtrack by removing matchstick from side

⏱

Complexity

TimeO(4^n)

SpaceO(n)

Each matchstick can be placed in one of 4 sides, leading to 4^n possibilities in worst case.

💡 For n=10, 4^10 = 1,048,576 operations, which is already expensive and impractical for larger n.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is essential to understand the problem's search space and why pruning is needed.

🧠

Backtracking with Sorting and Early Pruning

💡 Sorting matchsticks in descending order helps place larger sticks first, enabling early pruning and reducing unnecessary recursion.

Intuition

By placing the largest matchsticks first, we quickly detect invalid paths and prune them, avoiding exploring many useless branches.

Algorithm

1. Calculate total length and check divisibility by 4.
2. Sort matchsticks in descending order to place large sticks first.
3. Use backtracking to assign each matchstick to a side.
4. If a side exceeds target length, prune immediately.
5. Return true if all matchsticks are assigned and sides equal target.

💡 Sorting helps detect invalid assignments early, drastically reducing the search space compared to brute force.

</>

Code

from typing import List

def makesquare(matchsticks: List[int]) -> bool:
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    side = total // 4
    matchsticks.sort(reverse=True)
    sides = [0] * 4

    def backtrack(index):
        if index == len(matchsticks):
            return all(s == side for s in sides)
        for i in range(4):
            if sides[i] + matchsticks[index] <= side:
                sides[i] += matchsticks[index]
                if backtrack(index + 1):
                    return True
                sides[i] -= matchsticks[index]
            if sides[i] == 0:
                break
        return False

    return backtrack(0)

# Driver code
if __name__ == '__main__':
    print(makesquare([1,1,2,2,2]))  # True
    print(makesquare([3,3,3,3,4]))  # False

Line Notes

matchsticks.sort(reverse=True)Sort descending to place large sticks first for early pruning

if sides[i] + matchsticks[index] <= side:Only place if side length not exceeded

if backtrack(index + 1):Recurse to next matchstick; propagate success

if sides[i] == 0:If side is empty and failed, no need to try other empty sides

sides[i] -= matchsticks[index]Backtrack by removing matchstick from side

import java.util.*;

public class MatchsticksToSquare {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = total / 4;
        Arrays.sort(matchsticks);
        reverse(matchsticks);
        int[] sides = new int[4];
        return backtrack(matchsticks, sides, 0, side);
    }

    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    }

    private boolean backtrack(int[] matchsticks, int[] sides, int index, int side) {
        if (index == matchsticks.length) {
            for (int s : sides) if (s != side) return false;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, index + 1, side)) return true;
                sides[i] -= matchsticks[index];
            }
            if (sides[i] == 0) break;
        }
        return false;
    }

    public static void main(String[] args) {
        MatchsticksToSquare solver = new MatchsticksToSquare();
        System.out.println(solver.makesquare(new int[]{1,1,2,2,2})); // true
        System.out.println(solver.makesquare(new int[]{3,3,3,3,4})); // false
    }
}

Line Notes

Arrays.sort(matchsticks);Sort ascending before reversing to descending

reverse(matchsticks);Reverse array to get descending order for pruning

if (sides[i] + matchsticks[index] <= side) {Place matchstick only if side length not exceeded

if (sides[i] == 0) break;Prune: if empty side fails, no need to try other empty sides

sides[i] -= matchsticks[index];Backtrack by removing matchstick

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        int side = total / 4;
        sort(matchsticks.rbegin(), matchsticks.rend());
        vector<int> sides(4, 0);
        return backtrack(matchsticks, sides, 0, side);
    }

private:
    bool backtrack(vector<int>& matchsticks, vector<int>& sides, int index, int side) {
        if (index == matchsticks.size()) {
            for (int s : sides) if (s != side) return false;
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, sides, index + 1, side)) return true;
                sides[i] -= matchsticks[index];
            }
            if (sides[i] == 0) break;
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {1,1,2,2,2};
    vector<int> test2 = {3,3,3,3,4};
    cout << boolalpha << sol.makesquare(test1) << "\n"; // true
    cout << boolalpha << sol.makesquare(test2) << "\n"; // false
    return 0;
}

Line Notes

sort(matchsticks.rbegin(), matchsticks.rend());Sort descending to place large sticks first

if (sides[i] + matchsticks[index] <= side) {Place matchstick only if side length not exceeded

if (backtrack(...)) return true;If successful assignment found, return true

if (sides[i] == 0) break;Prune: if empty side fails, no need to try other empty sides

sides[i] -= matchsticks[index];Backtrack by removing matchstick

function makesquare(matchsticks) {
    const total = matchsticks.reduce((a,b) => a+b, 0);
    if (total % 4 !== 0) return false;
    const side = total / 4;
    matchsticks.sort((a,b) => b - a);
    const sides = [0,0,0,0];

    function backtrack(index) {
        if (index === matchsticks.length) {
            return sides.every(s => s === side);
        }
        for (let i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= side) {
                sides[i] += matchsticks[index];
                if (backtrack(index + 1)) return true;
                sides[i] -= matchsticks[index];
            }
            if (sides[i] === 0) break;
        }
        return false;
    }

    return backtrack(0);
}

// Test cases
console.log(makesquare([1,1,2,2,2])); // true
console.log(makesquare([3,3,3,3,4])); // false

Line Notes

matchsticks.sort((a,b) => b - a);Sort descending to place large sticks first

if (sides[i] + matchsticks[index] <= side) {Place matchstick only if side length not exceeded

if (backtrack(index + 1)) return true;If successful assignment found, return true

if (sides[i] === 0) break;Prune: if empty side fails, no need to try other empty sides

sides[i] -= matchsticks[index];Backtrack by removing matchstick

⏱

Complexity

TimeO(k^n) with pruning (k < 4)

SpaceO(n)

Sorting and pruning reduce the search space drastically compared to brute force, but worst case remains exponential.

💡 For n=15, pruning can reduce operations from billions to millions, making it feasible in practice.

Interview Verdict: Accepted / Practical for interviews

This approach is efficient enough for typical constraints and demonstrates good problem-solving skills.

🧠

Backtracking with Bitmask and Memoization

💡 Using bitmask to represent used matchsticks and memoizing states avoids recomputing the same subproblems, improving efficiency.

Intuition

Represent the set of used matchsticks as a bitmask and store results for each state to avoid repeated work.

Algorithm

1. Calculate total length and check divisibility by 4.
2. Sort matchsticks descending for pruning.
3. Use a recursive function with parameters: current bitmask of used sticks and current side length.
4. Try to place unused matchsticks in current side without exceeding target.
5. Memoize results for each bitmask to avoid recomputation.
6. Return true if all matchsticks are used and sides are formed.

💡 Bitmasking compresses the state space, and memoization prevents repeated exploration of identical states.

</>

Code

from typing import List

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

    def backtrack(used_mask, curr_sum, sides_formed):
        if sides_formed == 3:
            return True
        if (used_mask, curr_sum, sides_formed) in memo:
            return memo[(used_mask, curr_sum, sides_formed)]
        for i in range(n):
            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):
                            memo[(used_mask, curr_sum, sides_formed)] = True
                            return True
                    else:
                        if backtrack(next_mask, next_sum, sides_formed):
                            memo[(used_mask, curr_sum, sides_formed)] = True
                            return True
        memo[(used_mask, curr_sum, sides_formed)] = False
        return False

    return backtrack(0, 0, 0)

# Driver code
if __name__ == '__main__':
    print(makesquare([1,1,2,2,2]))  # True
    print(makesquare([3,3,3,3,4]))  # False

Line Notes

memo = {}Memo dictionary to store results of states to avoid recomputation

def backtrack(used_mask, curr_sum, sides_formed):Recursive function with bitmask state and current side sum

if sides_formed == 3:If 3 sides formed, last side must be valid, return True

if (used_mask, curr_sum, sides_formed) in memo:Return memoized result if state seen before

if not (used_mask & (1 << i))Check if matchstick i is unused

next_mask = used_mask | (1 << i)Mark matchstick i as used in bitmask

if next_sum == side:If current side completed, move to next side

memo[(used_mask, curr_sum, sides_formed)] = FalseMemoize failure for current state

import java.util.*;

public class MatchsticksToSquare {
    private Map<String, Boolean> memo = new HashMap<>();
    private int[] matchsticks;
    private int side;
    private int n;

    public boolean makesquare(int[] matchsticks) {
        this.matchsticks = matchsticks;
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        side = total / 4;
        n = matchsticks.length;
        Arrays.sort(matchsticks);
        reverse(matchsticks);
        return backtrack(0, 0, 0);
    }

    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++; j--;
        }
    }

    private boolean backtrack(int usedMask, int currSum, int sidesFormed) {
        if (sidesFormed == 3) return true;
        String key = usedMask + "," + currSum + "," + sidesFormed;
        if (memo.containsKey(key)) return memo.get(key);
        for (int i = 0; i < n; i++) {
            if ((usedMask & (1 << i)) == 0) {
                int nextSum = currSum + matchsticks[i];
                if (nextSum <= side) {
                    int nextMask = usedMask | (1 << i);
                    if (nextSum == side) {
                        if (backtrack(nextMask, 0, sidesFormed + 1)) {
                            memo.put(key, true);
                            return true;
                        }
                    } else {
                        if (backtrack(nextMask, nextSum, sidesFormed)) {
                            memo.put(key, true);
                            return true;
                        }
                    }
                }
            }
        }
        memo.put(key, false);
        return false;
    }

    public static void main(String[] args) {
        MatchsticksToSquare solver = new MatchsticksToSquare();
        System.out.println(solver.makesquare(new int[]{1,1,2,2,2})); // true
        System.out.println(solver.makesquare(new int[]{3,3,3,3,4})); // false
    }
}

Line Notes

private Map<String, Boolean> memo = new HashMap<>();Memo map to store results of states

String key = usedMask + "," + currSum + "," + sidesFormed;Create unique key for memoization

if ((usedMask & (1 << i)) == 0)Check if matchstick i is unused

int nextMask = usedMask | (1 << i);Mark matchstick i as used

if (nextSum == side)If current side completed, move to next side

memo.put(key, true);Memoize success for current state

memo.put(key, false);Memoize failure for current state

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int side, n;
    vector<int> matchsticks;
    unordered_map<int, bool> memo;

    bool makesquare(vector<int>& ms) {
        matchsticks = ms;
        int total = 0;
        for (int m : matchsticks) total += m;
        if (total % 4 != 0) return false;
        side = total / 4;
        n = matchsticks.size();
        sort(matchsticks.rbegin(), matchsticks.rend());
        return backtrack(0, 0, 0, 0);
    }

private:
    bool backtrack(int usedMask, int currSum, int sidesFormed, int depth) {
        if (sidesFormed == 3) return true;
        int key = (usedMask << 8) | currSum; // Shift by 8 bits to combine uniquely
        if (memo.count(key)) return memo[key];
        for (int i = 0; i < n; i++) {
            if ((usedMask & (1 << i)) == 0) {
                int nextSum = currSum + matchsticks[i];
                if (nextSum <= side) {
                    int nextMask = usedMask | (1 << i);
                    if (nextSum == side) {
                        if (backtrack(nextMask, 0, sidesFormed + 1, depth + 1)) {
                            memo[key] = true;
                            return true;
                        }
                    } else {
                        if (backtrack(nextMask, nextSum, sidesFormed, depth + 1)) {
                            memo[key] = true;
                            return true;
                        }
                    }
                }
            }
        }
        memo[key] = false;
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> test1 = {1,1,2,2,2};
    vector<int> test2 = {3,3,3,3,4};
    cout << boolalpha << sol.makesquare(test1) << "\n"; // true
    cout << boolalpha << sol.makesquare(test2) << "\n"; // false
    return 0;
}

Line Notes

unordered_map<int, bool> memo;Memo map to store results of states

int key = (usedMask << 8) | currSum;Create unique key combining usedMask and currSum with shift and OR

if ((usedMask & (1 << i)) == 0)Check if matchstick i is unused

int nextMask = usedMask | (1 << i);Mark matchstick i as used

if (nextSum == side)If current side completed, move to next side

memo[key] = true;Memoize success for current state

memo[key] = false;Memoize failure for current state

function makesquare(matchsticks) {
    const total = matchsticks.reduce((a,b) => a+b, 0);
    if (total % 4 !== 0) return false;
    const side = total / 4;
    matchsticks.sort((a,b) => b - a);
    const n = matchsticks.length;
    const memo = new Map();

    function backtrack(usedMask, currSum, sidesFormed) {
        if (sidesFormed === 3) return true;
        const key = usedMask + ',' + currSum + ',' + sidesFormed;
        if (memo.has(key)) return memo.get(key);
        for (let i = 0; i < n; i++) {
            if ((usedMask & (1 << i)) === 0) {
                const nextSum = currSum + matchsticks[i];
                if (nextSum <= side) {
                    const nextMask = usedMask | (1 << i);
                    if (nextSum === side) {
                        if (backtrack(nextMask, 0, sidesFormed + 1)) {
                            memo.set(key, true);
                            return true;
                        }
                    } else {
                        if (backtrack(nextMask, nextSum, sidesFormed)) {
                            memo.set(key, true);
                            return true;
                        }
                    }
                }
            }
        }
        memo.set(key, false);
        return false;
    }

    return backtrack(0, 0, 0);
}

// Test cases
console.log(makesquare([1,1,2,2,2])); // true
console.log(makesquare([3,3,3,3,4])); // false

Line Notes

const memo = new Map();Memo map to store results of states

const key = usedMask + ',' + currSum + ',' + sidesFormed;Create unique key for memoization

if ((usedMask & (1 << i)) === 0)Check if matchstick i is unused

const nextMask = usedMask | (1 << i);Mark matchstick i as used

if (nextSum === side)If current side completed, move to next side

memo.set(key, true);Memoize success for current state

memo.set(key, false);Memoize failure for current state

⏱

Complexity

TimeO(n * 2^n)

SpaceO(2^n)

Memoization reduces repeated states, but worst case explores subsets represented by bitmask.

💡 For n=15, 2^15=32768 states, which is feasible with memoization and pruning.

Interview Verdict: Accepted / Efficient for interview constraints

This approach is optimal for the problem size and shows mastery of bitmasking and memoization.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 is the best balance for most interviews; approach 3 is optimal but more complex to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(4^n)	O(n)	Yes (deep recursion)	N/A	Mention only - never code
2. Backtracking with Sorting and Pruning	O(k^n) with pruning (k < 4)	O(n)	Possible but less likely	N/A	Code this approach in 95% of interviews
3. Backtracking with Bitmask and Memoization	O(n * 2^n)	O(2^n)	Less likely due to memoization	Yes	Use if comfortable with bitmasking and memoization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and confirm input/output format.State brute force approach and its limitations.Introduce sorting and pruning to optimize backtracking.Explain bitmasking and memoization for further optimization.Code the chosen approach carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 3min. Total ~25min

What the Interviewer Tests

Ability to identify backtracking, implement pruning, use sorting effectively, and optimize with bitmasking and memoization.

Common Follow-ups

• What if you need to form a rectangle instead of a square? → Adjust target sides accordingly.
• How to handle very large input sizes? → Use heuristics or approximate algorithms.

💡 These follow-ups test adaptability and understanding of problem variations.

🔍

Pattern Recognition

When to Use

1) Need to partition array into equal sum subsets, 2) Use all elements exactly once, 3) Backtracking with pruning is suitable, 4) Bitmasking can optimize state tracking.

Signature Phrases

form a squareuse all matchsticks exactly onceequal length sides

NOT This Pattern When

Knapsack problems or subset sum without equal partition constraints

Similar Problems

Partition to K Equal Sum Subsets - generalizes this problem to k subsetsSplit Array into Equal Sum Subsets - similar partitioning challengeTiling a Rectangle with Squares - spatial partitioning with constraints

Practice

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

2. The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:

def combinationSum(candidates, target):
    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):
            path += [candidates[index]] * count
            backtrack(index + 1, path, target - candidates[index] * count)
            # Missing path restoration here
    backtrack(0, [], target)
    return result

medium

A. Line with 'path += [candidates[index]] * count' because path is modified without backtracking (pop).

B. Line with 'candidates.sort()' because sorting is unnecessary.

C. Line with 'if target == 0:' because it should check for target <= 0.

D. Line with 'max_use = target // candidates[index]' because integer division may cause errors.

Solution

1. Step 1: Analyze path modification in loop

   Path is extended by count copies of candidates[index] but never restored after recursive call, causing path to grow incorrectly across iterations.

2. Step 2: Identify missing backtracking step

   Proper backtracking requires removing added elements after recursion to restore path state for next iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modifying path without restoration leads to incorrect combinations [OK]

Hint: Always restore path after recursion in backtracking [OK]

Common Mistakes:

• Forgetting to pop elements after recursion
• Assuming path copy avoids mutation issues

3. What is the time complexity of the space-optimized DP solution for counting subsets with sum K, given an array of size n and target sum K?

medium

A. O(2^n) because all subsets are explored

B. O(n * K) because the DP iterates over n elements and sums up to K

C. O(n + K) because it processes each element and sum once

D. O(n * K^2) because nested loops iterate over n and K twice

Solution

1. Step 1: Identify loops in the DP

   Outer loop runs n times, inner loop runs up to K times for each element.

2. Step 2: Calculate total operations

   Total operations = n * K, so time complexity is O(n * K).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP iterates over all elements and sums up to K -> O(n * K) [OK]

Hint: DP complexity depends on n and K, not exponential [OK]

Common Mistakes:

• Confusing DP with brute force exponential time
• Assuming linear time due to single loops

4. What is the time complexity of the backtracking with bitmask memoization approach for partitioning an array of size n into k equal sum subsets?

medium

A. O(k^n) because each element can go into any of k subsets

B. O(n * 2^n) due to exploring all subset states with memoization

C. O(n^2) because of sorting and nested loops

D. O(2^n) ignoring the linear factor from iteration

Solution

1. Step 1: Identify state space size

   Bitmask represents subsets of elements, so 2^n states possible.

2. Step 2: Analyze per-state work

   For each state, we iterate over n elements to try adding unused elements, so O(n) per state.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time complexity is O(n * 2^n) due to bitmask states and iteration [OK]

Hint: Bitmask states are 2^n, each checked with n iterations [OK]

Common Mistakes:

• Confusing brute force O(k^n) with memoized approach
• Ignoring linear factor in complexity

5. What is the time complexity of generating all subsets of an array of size n using the bit manipulation approach shown below?

medium

A. O(2^n * n) because for each of the 2^n masks, we check n bits to build the subset

B. O(2^n) because there are 2^n subsets and each subset is generated in constant time

C. O(n^2) because of nested loops over n elements

D. O(n * 2^n) because each of the 2^n subsets requires iterating over n elements

Solution

1. Step 1: Identify outer loop complexity

   The outer loop runs 2^n times, once per subset mask.

2. Step 2: Identify inner loop complexity

   For each mask, the inner loop iterates n times to check each bit.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Total time is 2^n * n due to mask and bit checks [OK]

Hint: Each subset requires checking n bits -> O(n*2^n) [OK]

Common Mistakes:

• Assuming subset generation is O(2^n) ignoring bit checks
• Confusing n^2 with 2^n * n