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 candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

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

3. Given the following code to generate subsets, what is the value of result after processing num=2 when nums = [1, 2]?

easy

A. [[], [1], [2]]

B. [[], [1], [1, 2], [2]]

C. [[], [1], [2], [1, 2], [2, 2]]

D. [[], [1], [2], [1, 2]]

Solution

1. Step 1: Trace result after processing num=1

   Initially result = [[]]. After num=1, new_subsets = [[1]], result = [[], [1]].

2. Step 2: Trace result after processing num=2

   For each subset in [[], [1]], add 2: new_subsets = [[2], [1, 2]]. Extend result: [[], [1], [2], [1, 2]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All subsets of [1,2] are present exactly once [OK]

Hint: Iterative subsets double result size each iteration [OK]

Common Mistakes:

• Forgetting to add subsets with current num
• Appending duplicates
• Wrong order of subsets

4. Consider the following Python code that generates all subsets of nums = [1, 2, 3]. What is the value of subset when mask = 5 during the iteration?

easy

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3]

Solution

1. Step 1: Convert mask=5 to binary

   5 in binary is 101, meaning bits 0 and 2 are set.

2. Step 2: Map bits to indices in nums

   Bit 0 corresponds to nums[0]=1, bit 2 corresponds to nums[2]=3, so subset = [1, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mask 5 selects elements at positions 0 and 2 -> [1, 3] [OK]

Hint: Mask bits correspond to included elements [OK]

Common Mistakes:

• Off-by-one bit indexing
• Confusing mask bits with element values

5. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities