Повторяющаяся часть вашего кода работает нормально.Есть только два небольших недостатка в довольно периферийных частях:
Два подмножества существуют, только если сумма чисел четна.Ваш код не учитывает это требование, которое является причиной сбоя в отношении {1,3,4,7}.Для этого тело основной функции немного изменено, так что повторение выполняется только для четных сумм.
Вы должны отсортировать дубликаты, которые предотвратят повторения, касающиеся {1,2,3,4,2} и {1,1,3,3,2,8}.Для этого результирующие подмножества должны быть просто сохранены.Затем, после удаления дубликатов, остальные подмножества распечатываются.Для удобства обе функциональные возможности заключены в добавленный SubsetPair-класс, который предоставляет методы storeSubsetPair и printSubsetPairList для хранения и печати соответственно.
Измененный код:
import java.util.*;
public class Main {
public static void main(String[] args) {
int arr[] = {1,3,4,7};
int sum = getSum(arr, arr.length);
int[] solution = new int[arr.length];
// find(arr, 0, 0, sum, solution); // REPLACED WITH: -----------------
if (sum % 2 == 0) {
sum = Math.round(sum / 2f);
find(arr, 0, 0,sum, solution);
}
SubsetPair.printSubsetPairList();
// -------------------------------------------------------------------
}
public static int getSum(int arr[], int n) {
// float sum = 0f; // REPLACED WITH: ---------------------------------
int sum = 0;
// -------------------------------------------------------------------
for (int i = 0; i < n; i++)
sum = sum + arr[i];
// return Math.round(sum / 2); // REPLACED WITH: ---------------------
return sum;
// -------------------------------------------------------------------
}
public static void find(int[] A, int currSum, int index, int sum,
int[] solution) {
if (currSum == sum) {
// System.out.println("\nSum found"); // REPLACED WITH: ----------
// for (int i = 0; i < solution.length; i++) {
// if (solution[i] == 1) {
// System.out.print(" " + A[i]);
// }
// }
SubsetPair.storeSubsetPair(A, solution);
// ---------------------------------------------------------------
} else if (index == A.length) {
return;
} else {
solution[index] = 1;// select the element
currSum += A[index];
find(A, currSum, index + 1, sum, solution);
currSum -= A[index];
solution[index] = 0;// do not select the element
find(A, currSum, index + 1, sum, solution);
}
return;
}
}
//NEW: Class for storage and print:
class SubsetPair {
private static List<SubsetPair> subsetPairList = new ArrayList<>();
private List<Integer> subset1 = new ArrayList<>();
private List<Integer> subset2 = new ArrayList<>();
//
// Storage of the subset pair
//
public static void storeSubsetPair(int[] A, int[] solution) {
SubsetPair subsetPair = new SubsetPair();
for (int i = 0; i < solution.length; i++) {
if (solution[i] == 1) {
subsetPair.subset1.add(A[i]);
} else {
subsetPair.subset2.add(A[i]);
}
}
if (!subsetPair.isDuplicate()) {
subsetPairList.add(subsetPair);
}
}
// Remove duplicates
private boolean isDuplicate() {
for (SubsetPair subsetPair : subsetPairList) {
if (isEqual(subset1, subsetPair.subset2) && isEqual(subset2, subsetPair.subset1) ||
isEqual(subset1, subsetPair.subset1) && isEqual(subset2, subsetPair.subset2)) {
return true;
}
}
return false;
}
private boolean isEqual(List<Integer> subset1, List<Integer> subset2) {
return subset1.containsAll(subset2) && subset2.containsAll(subset1);
}
//
// Output of the subset pairs
//
public static void printSubsetPairList() {
if (subsetPairList.size() == 0) {
System.out.println("No subset-pairs found!");
} else {
for (int i = 0; i < subsetPairList.size(); i++) {
subsetPairList.get(i).printSubsetPair(i + 1);
}
}
}
private void printSubsetPair(int i) {
System.out.print(i + ". Subset-Pair:\n");
System.out.print("Subset 1: ");
for (Integer i1 : subset1) {
System.out.print(i1 + " ");
}
System.out.println();
System.out.print("Subset 2: ");
for (Integer i2 : subset2) {
System.out.print(i2 + " ");
}
System.out.print("\n\n");
}
}
С этими изменениями получается:
Для {1,2,3,4,2} с четной суммой 12:
1. Subset-Pair:
Subset 1: 1 2 3
Subset 2: 4 2
Для {1,1,3, 3,2,8} с четной суммой 18:
1. Subset-Pair:
Subset 1: 1 3 3 2
Subset 2: 1 8
для {1,3,4,7} с нечетной суммой 15:
No subset-pairs found!
для{3,1,1,2,2,1} с четной суммой 10:
1. Subset-Pair:
Subset 1: 3 1 1
Subset 2: 2 2 1
2. Subset-Pair:
Subset 1: 3 2
Subset 2: 1 1 2 1
Для {2,4,8} с четной суммой 14:
No subset-pairs found!
Как уже отмечалось в комментариях, проблема связана с «проблемой разбиения», которая представляет собой задачу решить, можно ли разбить мультимножество натуральных чисел на два подмножества с равной суммой.Это подробно объясняется, например, в https://en.wikipedia.org/wiki/Partition_problem или в https://www.geeksforgeeks.org/partition-problem-dp-18/ (последняя включает реализацию Java).Но обе проблемы не совсем идентичны , потому что решение "проблемы разбиения" просто отвечает на вопрос , если мультимножество может быть разбито на два подмножества, но не явно определяют сами подмножества.