华为OD机试 - 等和子数组最小和 - 深度优先搜索（Java 2022 Q4 100分）

在这里插入图片描述

专栏导读

本专栏收录于《华为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;}
}