题解 | 拼接木棍

import java.io.*;
import java.util.*;

public class Main {
   // n: 小木棒总数, sum: 所有木棒总长度, targetL: 目标原始长度, numbers: 目标原始木棒根数
    private static int n, sum, targetL, numbers;
    private static Integer[] a; // 存储砍断后的小木棒长度

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine().trim());
        String[] s = br.readLine().trim().split("\\s+");
        a = new Integer[n];
        boolean[] used = new boolean[n]; // 标记每根小木棒是否已被乔治使用
        sum = 0;
        int maxL = 0;

        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
            sum += a[i];
            maxL = Math.max(maxL, a[i]); // 原始长度至少要等于最长的那根小木棒
        }

        // 【剪枝优化 1】：降序排序。
        // 优先尝试长木棒。因为长木棒对位置要求更苛刻，如果它拼不通，能更早触发回溯。
        Arrays.sort(a, (x1, x2) -> (x2 - x1));

        // 枚举原始木棒可能的长度 targetL
        // 范围：从最长的那根开始，直到所有木棒的总和
        for (targetL = maxL; targetL <= sum; targetL++) {

            // 【条件约束】：原始长度必须能被总长度整除，否则乔治不可能拼成同样长的木棒
            if (sum % targetL != 0) {
                continue;
            }

            numbers = sum / targetL; // 计算在当前 targetL 下应该拼出多少根

            // 尝试拼凑，初始：已完成0根，当前长度0，从第0个小木棒开始找
            if (dfs(0, 0, 0, used)) {
                out.println(targetL); // 找到第一个可行的最小长度，即为答案
                break;
            }
        }
        out.flush();
        out.close();
        br.close();
    }

    /**
     * DFS 拼凑过程
     *
     * @param completed 已完整拼好的原始木棒根数
     * @param currentL  当前正在拼的那根原始木棒已经达到的长度
     * @param idx       为了避免重复组合，从数组的哪一个下标开始挑选下一根小木棒
     * @param used      使用情况记录
     */
    private static boolean dfs(int completed, int currentL, int idx, boolean[] used) {
        // 【递归出口】：如果乔治拼好了所有原始木棒，大功告成
        if (completed == numbers) {
            return true;
        }

        // 如果当前这根拼满了，开启下一根木棒的拼凑
        if (currentL == targetL) {
            return dfs(completed + 1, 0, 0, used);
        }

        for (int i = idx; i < n; i++) {
            // 如果这根用过了，或者放进去就超过了目标长度，跳过
            if (used[i] || currentL + a[i] > targetL) {
                continue;
            }

            // 【做选择】：尝试放这根木棒
            used[i] = true;
            if (dfs(completed, currentL + a[i], i + 1, used)) {
                return true;
            }

            // 【撤销选择】：刚才的尝试失败了，拿出来
            used[i] = false;

            // --- 核心剪枝策略 (极其关键) ---

            // 【剪枝优化 2】：首棒失败判定
            // 如果此时 currentL 为 0，说明我们正在尝试拼一根新木棒的第一部分。
            // 如果第一部分用这根最长的木棒都拼不出来，那后面更拼不出来了。

            // 【剪枝优化 3】：末棒失败判定
            // 如果加上这根木棒刚好填满了 targetL，但在后续递归中失败了，
            // 说明用这根刚好填满的方案不行，那么换用几根更碎的小木棒来填这个坑也肯定不行。
            if (currentL == 0 || currentL + a[i] == targetL) {
                return false;
            }

            // 【剪枝优化 4】：去重剪枝
            // 如果当前长度的木棒不行，那后面相同长度的木棒也肯定不行，直接跳过。
            while (i + 1 < n && a[i + 1].equals(a[i])) {
                i++;
            }
        }
        return false;
    }
}