1027MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Fencing a Square From Every Rod

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A pile of rods has the lengths rods. Every rod has to be used exactly once, laid end to end without being broken or bent, and the rods must be grouped into the four sides of a square.

Return whether that is possible.

Examples

Example 1

Input: rods = [5, 5, 5, 5, 4, 4, 4, 4]
Output: true

The lengths add to thirty-six, so each side must come to nine, which is one rod of 5 laid with one rod of 4. There are four of each, so the four sides come out alike.

Example 2

Input: rods = [4, 4, 3, 3, 3, 3]
Output: false

The lengths add to twenty, so each side must come to five. No group of these rods comes to five: a 4 leaves one over and nothing is that short, a 3 leaves two over and nothing is that short either.

Example 3

Input: rods = [1, 2, 3, 4, 5]
Output: false

The lengths add to fifteen, which does not divide evenly by four, so no square is possible whatever the arrangement.

Constraints

1 <= rods.length <= 15
1 <= rods[i] <= 10^8

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def makesquare(rods: list[int]) -> bool:

Java

public boolean makesquare(int[] rods)

The intended approach

Time O(4^n) at worst for n rods, cut down heavily by the ordering and the pruning.Space O(n) for the walk's depth.

Add the lengths up. A side has to come to a quarter of the total, so if the total does not divide evenly by four nothing works, and neither does anything if a single rod is longer than that quarter. Otherwise fill the four sides by taking the rods one at a time, longest first, and trying each side that still has room for the rod in hand. Going longest first fails fast: a long rod that fits nowhere is found straight away rather than after a crowd of short rods has been arranged. One pruning matters. Two sides holding the same running length are interchangeable, so trying the same rod on both only repeats work. Keeping the lengths already tried for the rod in hand, and skipping a side whose running length is among them, cuts most of the repetition away. With at most fifteen rods this settles quickly, even though the worst case is still four raised to the number of rods.

Pythonentry point: makesquare

def makesquare(rods):
    total = 0
    for length in rods:
        total += length
    if total % 4:
        return False
    side = total // 4
    order = sorted(rods, reverse=True)
    if order[0] > side:
        return False
    filled = [0, 0, 0, 0]
    def place(at):
        if at == len(order):
            return True
        length = order[at]
        tried = set()
        for which in range(4):
            if filled[which] in tried:
                continue
            if filled[which] + length > side:
                continue
            tried.add(filled[which])
            filled[which] += length
            if place(at + 1):
                return True
            filled[which] -= length
        return False
    return place(0)

The obvious version

Go at it by sides rather than by rods. Work out which groups of rods come to exactly a quarter of the total, holding each group as a set of bits, then try every three of those groups that share no rod and check that whatever is left over also comes to a quarter. Costs the groups cubed rather than a walk over the rods.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_makesquare(rods):
    total = 0
    for length in rods:
        total += length
    if total % 4:
        return False
    side = total // 4
    n = len(rods)
    full = (1 << n) - 1
    weight = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & -mask
        at = low.bit_length() - 1
        weight[mask] = weight[mask ^ low] + rods[at]
    ones = []
    for mask in range(1 << n):
        if weight[mask] == side:
            ones.append(mask)
    for a in ones:
        for b in ones:
            if a & b:
                continue
            for c in ones:
                if c & (a | b):
                    continue
                if weight[full ^ (a | b | c)] == side:
                    return True
    return False

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in