题目链接：https://www.dotcpp.com/oj/problem2354.html

    体会：尝试了具有返回值dfs()函数的设计，以及强化了搜索问题的可行性、最优性的理解

    1. import java.util.*;
    2. public class Test{
    3.     public static int[] arr;
    4.     public static int cnt = 0; //记录长度<=50的小木棍数量
    5.     public static int sum = 0; //记录所有长度<=50的小木棍的长度之和
    6.     public static boolean[] visited; //标记小木棍的使用状态
    8.     public static boolean dfs(int targetCount, int nowCount, int nowSum, int len, int index){
    9.         //targetCount: 需要拼凑的木棍数量
    10.         //nowCount: 目前已经拼凑的数量
    11.         //nowSum: 当前由若干小木棍拼凑的长度
    12.         //len: 此次枚举的木棍长度
    13.         //index: 遍历的下标
    15.         if(nowCount == targetCount){ //所有小木棍恰好能拼凑出 targetCount根长度为len的木棍
    16.             return true;
    17.         }
    18.         if(nowSum == len){ //已经拼凑出一根长度为len的木棍，接着往下尝试
    19.             return dfs(targetCount, nowCount + 1, 0, len, cnt);
    20.         }
    22.         for(int i = index; i >= 0; i--){
    23.             if(!visited[i] && nowSum + arr[i] <= len){ //剪枝2：保证小木棍拼凑的长度 <= len
    24.                 visited[i] = true;
    25.                 if(dfs(targetCount, nowCount, nowSum + arr[i], len, i-1)){ //此处记得将dfs()的结果return
    26.                     return true;
    27.                 }
    28.                 visited[i] = false;
    29.                 //剪枝3：如果当前arr[i]尝试失败后(因为只有失败后才回溯到此处)，证明arr[i]对当前的结果无作用，直接跳过
    30.                 while(i > 0 && arr[i] == arr[i-1]) i--;
    31.             }
    33.         }
    34.         return false;
    35.     }
    36.     public static void main(String[] args) {
    37.         Scanner sc = new Scanner(System.in);
    38.         int n = sc.nextInt();
    39.         arr = new int[n+1];
    40.         visited = new boolean[n+1];
    42.         int num;
    43.         for(int i = 1; i <= n; i++){
    44.             num = sc.nextInt();
    45.             if(num <= 50){ //长度>50的小木棍全都抛弃，不然AC不了
    46.                 arr[++cnt] = num;
    47.                 sum += num;
    48.             }
    49.         }
    51.         //按从小到大排序，然后逆序遍历
    52.         Arrays.sort(arr, 1, cnt + 1);
    54.         //枚举切割前木棍的长度，其范围为[最长的小木棍长度，所有小木棍长度之和]
    55.         //注意这里说的小木棍都是指长度<=50的
    56.         for(int len = arr[cnt]; len <= sum; len++){
    57.             //剪枝1：sum必须能整除木棍的长度
    58.             if(sum % len == 0){
    59.                 Arrays.fill(visited, false);
    61.                 //切割前木棍的数量
    62.                 int k = sum / len;
    64.                 //我们需要去利用现有的小木棍，使其能刚好拼凑出k根长度为len的木棍
    65.                 //如果当前的方案能够生效，必然是最小的长度
    66.                 if(dfs(k, 0, 0, len, cnt)){
    67.                     System.out.println(len);
    68.                     return;
    69.                 }
    70.             }
    71.         }
    73.     }
    74. }