/*
输入
第一行 ：长度n 除数k
第二行： 数组元素
4 7 
4 0 1 3 
输出
1043
*/
public class MinInteeger {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		String[] arr = new String[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.next();
		}

		boolean[] dp = new boolean[n];
        //保留所有拼接数值
		Set<Integer> set = new HashSet<>();
        //拼接字符串
		String tmp = "";
        //深度优先拼接字符串
		for (int i = 0; i < n; i++) {
            //确保开头不为0
			if (!arr[i].equals("0")) {
				dfs(arr,i,0, tmp,dp,set);
			}
		}

		int min = Integer.MAX_VALUE;
        //遍历找能被整除的最小整数
		for (int i : set) {
			if (i % k == 0) {
				min =Math.min(min, i);
			}
		}
		System.out.println(min);
	}
    
    /**
	* @Param: index 待拼接字符下标
	* @Param: count 已拼接元素个数
	* @Param: tmp 拼接字符串
	* @Param: dp 标识是否遍历过
	*/
	private static void dfs(String[] arr, int index, int count, String tmp, boolean[] dp,Set<Integer> set) {
		tmp += arr[index];
		dp[index] = true;
		if(count == arr.length-1) set.add(Integer.parseInt(tmp));

		for (int i = 0; i < arr.length; i++) {
			if (!dp[i]) {
				dfs(arr,i,count+1, tmp,dp,set);
			}
		}
		dp[index] = false;
		tmp = tmp.substring(0, tmp.length()-arr[index].length());
	}
}

2. lc329. 矩阵中的最长递增路径

3. 给定长度为n的数组，找到一个最大素数，并且数组中部分元素相加可得到该素数

/*
输入：
第一行： 元素个数
第二行 元素值
5
1 3 5 7 9
输出最大素数：
19
*/
public class SingleValue {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];

		int sum = 0;//保留数组元素之和
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			sum += arr[i];
		}

		//保存选取元素之和
		Set<Integer> set = new HashSet<>();
		boolean[] dp = new boolean[n];
		int k = n;//选取元素个数
		while (k > 0) {
			for (int i = 0; i < n; i++) {
				dfs(arr, set, i, k, 0, dp);
			}
			//每次循环减少一个长度
			k--;
		}

		//标记是否存在该数,存在即输出该素数，不存在输出-1
		boolean existed = false;
		//根据sum倒序遍历，查询是否包含该素数值
		for (int i = sum; i > 0; i--) {
			if (set.contains(i) && isPrime(i)) {
				System.out.println(i);
				existed = true;
				break;
			}
		}
		if (!existed) System.out.println(-1);
	}

	private static boolean isPrime(int n) {
		for (int i = 2; i < n; i++) {
			if (n % i == 0) return false;
		}
		return true;
	}

    /**
	 * @Param: set 保留所有添加元素之和
	 * @Param: index 待添加元素索引
	 * @Param: k 待添加元素数目
	 * @Param: sum 已添加元素之和
	 */
	private static void dfs(int[] arr, Set<Integer> set, int index, int k, int sum, boolean[] dp) {
		sum += arr[index];
		dp[index] = true;
		if (k == 1) set.add(sum);

		for (int i = 0; i < arr.length; i++) {
			if (!dp[i]) {
				dfs(arr, set, i, k - 1, sum, dp);
			}
		}
		sum -= arr[index];
		dp[index] = false;
	}
}