题解 | #数组分组#
数组分组
http://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86
//非常标准的递归思路
import java.util.*;
public class Main {
//在全局判断，不用返回值；后续优化可根据flag做减枝操作
public static boolean flag;
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
flag = false;
recur(nums, 0, 0, 0);
System.out.println(flag);
}
}
public static void recur(int[] nums, int idx, int sum5, int sum3) {
if (idx == nums.length) {
if (sum5 == sum3) {
flag = true;
}
return;
}
if (nums[idx] % 5 == 0) {
recur(nums, idx + 1, sum5 + nums[idx], sum3);
} else if (nums[idx] % 3 == 0 && nums[idx] % 5 != 0) {
recur(nums, idx + 1, sum5, sum3 + nums[idx]);
} else {
recur(nums, idx + 1, sum5 + nums[idx], sum3);
recur(nums, idx + 1, sum5, sum3 + nums[idx]);
}
}
}
