题目描述

dfs+剪枝

木棍长度可以从1开始枚举，这里我们直接从最大的木棒长度开始。可以减少一点枚举

样例

import java.util.*;

public class Main {
    static final int N = 70;
    //要用Integer才能自定义比较
    static Integer[] sticks = new Integer[N];
    //判断当前木棍是否被使用
    static boolean[] st = new boolean[N];

    static int n;

    //sum是木棒长度总合，length是木棍的长度
    static int sum, length;

    //u是拼好木棍的个数，cur代表当前的木棒拼好的长度，start表示木棒启始的下标
    static boolean dfs(int u, int cur, int start) {
        //拼好木棍的个数 * 木棍长度 = 木棒的长度总合 直接return true
        if (u * length == sum) return true;

        //当前的木棒拼好的长度等于木棍的长度，说明该条木棍拼好了，去拼下条木棍
        if (cur == length) return dfs(u + 1, 0, 0);


        for (int i = start; i < n; i++) {

            //如果当前的木棍被使用，就用下一个木棍
            if (st[i]) continue;

            //存储(使用)当前木棒的长度
            int l = sticks[i];

            //如果当前的木棍长度 + 当前的木棒拼好的长度 < 枚举的木棍长度
            if (cur + l <= length) {
                //改木棒被使用
                st[i] = true;
                //当前的木棒拼好的长度+当前的木棒的长度，去找下一个木棒(保证使用的木棒编号严格递增) 如果返回的true,也直接返回true
                if (dfs(u, cur + l, i + 1)) return true;
                //恢复现场 用过的木棒改为没用过
                st[i] = false;
            }

            //以下都是剪枝

            //如果放一个木棒就失败和放最后一个木棒就失败，就return false
            if (cur == 0 || cur + l == length) return false;

            //以下三行就是跳过当放一个木棒失败的时候，跳过和他相同长度的木棒
            int j = i + 1;

            while (j < n && sticks[j] == l) j++;

            i = j - 1;
        }

        return false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while ((n = scanner.nextInt()) != 0) {
            sum = length = 0;
            for (int i = 0; i < n; i++) {
                int l = scanner.nextInt();
                sticks[i] = l;
                sum += l;
                //找到最长的木棒 从最长的木棒开始枚举木棍的长度
                length = Math.max(length, l);
            }

            //木棒大小逆序排序
            Arrays.sort(sticks, 0, n, (a, b) -> b -a);

            //木棒是否被使用 初始化为false
            Arrays.fill(st, false);


            while (true) {
                //木棒的长度总合能被木棍长度整除
                if (sum % length == 0 && dfs(0, 0, 0)) {
                    System.out.println(length);
                    break;
                }
                //不符合条件就枚举下一个木棍长度
                length++;
            }
        }
    }

}