十二 167. 木棒 (回溯)

167. 木棒 (回溯)

思路：把最长木棒长度作为初始，逐渐增减，使用dfs寻找最小的可能初始长度。
需要注意的点就是剪枝：

1. 剪枝 1：sum % length == 0 只有 length 是 sum 的约数才有可能凑出多个等长的木棒
2. 剪枝 2：优化搜索顺序，木棍长度从大到小排序，可以减少搜索的分支
3. 排除等效冗余优化
   剪枝 3-1：确定每根木棒中木棍的枚举顺序，因为我们的方案和顺序没有关系，以组合的形式枚举方案可以少搜很多重复方案
   剪枝 3-2：如果当前木棍没有搜到方案，则跳过所有长度相等的木棍
   剪枝 3-3：如果是木棒的第一根木棍就搜索失败了，则一定搜不到方案
   剪枝 3-4：如果是木棒的最后一根木棍（+ 上它木棒长度正好是 length）搜索失败了，也一定搜不到方案

import java.util.*;

public class Main {
    private static int[] sticks;
    private static boolean[] used;
    private static int n;
    private static int sum;
    private static int length;
    
    private static boolean dfs(int u, int cur, int start) {
        if (u * length == sum) {
            return true;
        }
        if (cur == length) {
            return dfs(u + 1, 0, 0);
        }
        for (int i = start; i < n; i++) {
            if (used[i]) {
                continue;
            }
            if (cur + sticks[i] <= length) {
                used[i] = true;
                if (dfs(u, cur + sticks[i], i + 1)) {
                    return true;
                }
                used[i] = false;
            }
            if (cur == 0 || cur + sticks[i] == length) {
                return false;
            }
            int j = i + 1;
            while (j < n && sticks[j] == sticks[i]) {
                j++;
            }
            i = j - 1;
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while (n != 0) {
            sum = 0;
            length = 0;
            sticks = new int[n];
            for (int i = 0; i < n; i++) {
                sticks[i] = sc.nextInt();
                sum += sticks[i];
                length = Math.max(length, sticks[i]);
            }
            Arrays.sort(sticks);
            int left = 0, right = sticks.length - 1;
            while (left < right) {
                int temp = sticks[left];
                sticks[left] = sticks[right];
                sticks[right] = temp;
                left++;
                right--;
            }
            
            used = new boolean[n];
            while (true) {
                if (sum % length == 0 && dfs(0, 0, 0)) {
                    System.out.println(length);
                    break;
                }
                length++;
            }
            n = sc.nextInt();
        }
        
    }
}