public static boolean haveEqualSums(int[] input1, int[] input2) { 用Java的递归写

public static boolean haveEqualSums(int[] input1, int[] input2) {
return checkEqualSums(input1, 0, input1.length - 1, input2, 0, input2.length - 1);
}

private static boolean checkEqualSums(int[] input1, int start1, int end1, int[] input2, int start2, int end2) {
if (start1 > end1 && start2 > end2) { // both arrays are empty
return true;
}
if (start1 > end1 || start2 > end2) { // one array is empty while the other is not
return false;
}
int sum1 = 0;
for (int i = start1; i <= end1; i++) {
sum1 += input1[i];
}
int sum2 = 0;
for (int i = start2; i <= end2; i++) {
sum2 += input2[i];
}
if (sum1 != sum2) {
return false;
}
// recursively check subsets
for (int i = start1; i <= end1; i++) {
for (int j = start2; j <= end2; j++) {
if (input1[i] == input2[j]) {
if (checkEqualSums(input1, start1, i - 1, input2, start2, j - 1)
&& checkEqualSums(input1, i + 1, end1, input2, j + 1, end2)) {
return true;
}
}
}
}
return false;
}