题解 | #kotori和素因子#java

import java.util.Scanner;

import java.util.List;
import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static int result = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        List<Integer> list = new ArrayList<>();
	  //回车需要排除
        in.nextLine();
        String[] s = in.nextLine().split(" ");

        for (int i = 0; i < s.length; i++) {
            list.add(Integer.parseInt(s[i]));
        }

        List<List<Integer>> paramList = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            List<Integer> subList = new ArrayList<>();
            for (int j = 2; j <= list.get(i) / 2; j++) {
                if (list.get(i) % j == 0 && isSu(j)) {
                    subList.add(j);
                }
            }
		  //本身可能是素因子
            if (isSu(list.get(i))) {
                subList.add(list.get(i));
            }
            paramList.add(subList);

            // for (int k = 0; k < subList.size(); k++) {
            // System.out.print(subList.get(k) + " ");
            // }

            // System.out.println();
        }

        dfs(num, 0, paramList, new ArrayList<Integer>(), 0);
        if (result == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }

  /**
  * 判断是不是素因子
  **/
    private static boolean isSu(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

  /**
  * addedParams当前已经遍历层的元素列表
  * sum当前分支的结果
  * result当前已经遍历的所有分支的最小结果
  **/
    private static void dfs(int height, int y, List<List<Integer>> dataSource,
                            ArrayList<Integer> addedParams, int sum) {
        if (y == height) {
            result = Math.min(sum, result);
            return;
        }

        for (int i = 0; i < dataSource.get(y).size(); i++) {
            if (addedParams.contains(dataSource.get(y).get(i))) {
			  //当存在相同的素因子时，不进行下一层遍历；当continue以后for循环即结束时，result值不会发生变化，所以当result == Integer.MAX_VALUE时，认为存在相同的素因子
                continue;
            }
            addedParams.add(dataSource.get(y).get(i));
            dfs(height, y + 1, dataSource, addedParams, sum + dataSource.get(y).get(i));
		  	//排除兄弟节点的干扰
            addedParams.remove(dataSource.get(y).get(i));
        }

    }
}

//代码参考：https://blog.csdn.net/red_red_red/article/details/94199147