问题要用所有木棒恰好拼成四条等长边的正方形。设总长为 sum,若 sum % 4 != 0 必不可能;目标边长 target = sum / 4,若最大木棒 > target 同样不可能。将木棒按降序排序,优先放置长棒以尽早暴露冲突。
用位掩码 + 记忆化搜索描述状态:
mask 表示哪些木棒已被使用(n ≤ 20,可用一个 20 位二进制数表示);curr 表示当前正在填的这一条边的已用长度(0 ≤ curr < target)。
从 (mask, curr) 出发,枚举所有未使用的木棒 x,若 curr + x ≤ target 则递归到新状态 (mask | (1<<i), (curr + x) % target);当 mask 覆盖全部木棒时,若 curr == 0 说明刚好收尾(四边都被完整填充),返回可行。在一个被遗忘的古代文明中,流传着一个传说:只有能拼出“时间之框”的人才能打开通往未来的大门。
这个“时间之框”真实是一个正方形的边框,由若干根神秘木棒首尾相连组成,每一根都必须使用一次目仅用一次。
你是一位年轻的探验者,在遗迹深处找到了一盒装满木棒的盒子,并在石壁上看到了制作“时间之框”的 规则: