题解 | #数组分组#
又是一道dfs的经典题。
注意几个特殊条件
1）sum/2不能整除；
2）输入为5 -5，即sum = 0, target = 0;
import java.util.*;
public class Main {
public static void main(String[] args) {
// 将非5 非3 倍数的数字分为两组，使其差值为5和3组的差值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum3 = 0, sum5 = 0, sum = 0;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
sum += num;
if (num % 5 == 0) {
sum5 += num;
continue;
} else if (num % 3 == 0) {
sum3 += num;
continue;
} else {
list.add(num);
}
}
if (sum % 2 != 0) {
System.out.println("false");
return;
}
int target = sum / 2 - sum5;
if (list.size() == 0 && target == 0) {
System.out.println("true");
return;
}
if (list.size() == 1) {
if (list.get(0) != target) {
System.out.println("false");
} else {
System.out.println("true");
}
return;
}
int[] nums = new int[list.size()];
for (int i = 0; i < nums.length; i++) {
nums[i] = list.get(i);
}
// 组合，m个数据边选择x个数据(不可重复取)，使其和为target
// 再次安排dfs
for (int tag = 1; tag <= nums.length; tag++) {
List<List<Integer>> arrange = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
dfs(arrange, tmp, nums, visited, tag, 0);
for (List<Integer> tmpList : arrange) {
int sumList = 0;
for (Integer integer : tmpList) {
sumList += integer;
if (sumList == target) {
System.out.println("true");
return;
}
}
}
}
System.out.println("false");
}
/**
* 因为需要选择x个数求和，因此只需要组合即可，不需要排列
*/
public static void dfs(List<List<Integer>> arrange, List<Integer> tmp, int[] nums,
boolean[] visited, int tag, int cur) {
if (tmp.size() == tag) {
arrange.add(new ArrayList<>(tmp));
return;
}
for (int i = cur; i < nums.length; i++) {
if (!visited[i]) {
tmp.add(nums[i]);
visited[i] = true;
dfs(arrange, tmp, nums, visited, tag,i + 1);
// 回溯
visited[i] = false;
tmp.remove(tmp.size() - 1);
}
}
}
}
