专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。
二、输入描述
第一行输入 m
接着输入m个数，表示此数组nums
数据范围：1<=m<=50, 1<=nums[i]<=50
三、输出描述
最小拆分数组和。
四、解题思路
虽然题意很简单，看着很简单，其实这道题是有点难度的，100分你能抽到这道题，自求多福吧，兄弟。
比如：
4 3 2 3 5 2 1
可以组合成
4 1
3 2
3 2
5
解题思路：
1、答案一定在最大值与所有数的和之间，拿到这个值看是否能够满足条件；
2、用深度优先搜索，搜索一种方法满足子数组合能够满足target值的解；
3、每次从上一次找的数后面的数开始递归，这个优化非常重要，不加的话会把之前的结果再找一遍，例如，我本次递归取了第2个数，然后下面再取第5个数，当我下次递归取了第5个数的时候，如果不从第5个数之后来选，就会搜到上面一样取到第二个数，那里的结果我们之前是已经搜索过了的。
五、Java算法源码
package com.guor.od;
import java.util.Scanner;
import java.util.*;
public class OdTest05 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = Integer.valueOf(sc.nextLine());
int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(nums);
// 求和
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
// 答案一定在最大值与所有数的和之间，拿到这个值看是否能够满足条件
for (int ans = nums[nums.length - 1]; ans <= sum; ans++) {
if (dfs(ans, 0, nums, new HashSet<>(), 0)) {
System.out.println(ans);
break;
}
}
}
/**
* 用深度优先搜索，搜索一种方法满足子数组合能够满足target值的解
*
* @param target 目标值
* @param nowValue 当前递归中的数组和
* @param nums 数组
* @param useIndex 数组中已经使用过的数的下标
* @param nowIndex 上一个取的数下标，用于搜索剪枝
* @return 是否找到了答案
*/
public static boolean dfs(int target, int nowValue, int[] nums, Set<Integer> useIndex, int nowIndex) {
if (useIndex.size() == nums.length && nowValue == 0) {
//只有当数组中的值已经用完，且没有剩下数的时候，说明答案已经找到了
return true;
}
//每次从上一次找的数后面的数开始递归，这个优化非常重要，不加的话会把之前的结果再找一遍，
//例如，我本次递归取了第2个数，然后下面再取第5个数，
//当我下次递归取了第5个数的时候，如果不从第5个数之后来选，就会搜到上面一样取到第二个数，那里的结果我们之前是已经搜索过了的
for (int i = nowIndex; i < nums.length; i++) {
if (useIndex.contains(i)) {
//表示这个数已经被用过了
continue;
}
//只有当当前取的数 + 当前的和小于目标值时才可以取
if (nowValue + nums[i] <= target) {
//标记这个数已经用过了
useIndex.add(i);
if (nowValue + nums[i] == target) {
//当前的和已经等于目标值，这个时候我们要从头来找一个没有用过的数来继续搜索
if (dfs(target, 0, nums, useIndex, 0)) {
return true;
}
} else {
//当前的和小于目标值，我们还得继续找数来继续填充我们的和
if (dfs(target, nowValue + nums[i], nums, useIndex, i)) {
return true;
}
}
useIndex.remove(i);
}
}
return false;
}
}
六、效果展示
1、输入
4 6 5 5 8 2 3 3 3 1
2、输出
8
🏆下一篇：华为OD机试 - 荒岛求生 - 栈Stack（Java 2023 B卷 100分）
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。