Your code is quite inefficient by storing all the sums of pairs into the hashmap.
The memory requirements grow exponentially (adding array entry n adds n more pairs, so it grows in a factorial manner).
You are better off by holding onto a pair only as long as you need it. This can be done by checking all possible additions to that pair at once and then throwing it away.
This is most easily done recursively. You have a set of numbers, and the next number you can either include in your set or not. Repeat this recursively.
Generally, for any given set of array values, you hold onto it only as long as you need it, to try combining it with other items from the array. Once you find a solution you save it. Once you've exhausted all possibilities with that set you throw it away.
public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();
public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not
//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last in the set
if(added == target) {// the sum matches, so it is a solution
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
solutions.add(next);
}
} else if(added <= target) {//use it if we can (the sum is not too large). This assumes all array values are positive, if negative values allowed, then remove the "if(added <= target)" condition
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}
public static void main(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int[0]);
}
}
That's all you need when you use the recursive approach. If you add code to print out the results as shown:
public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 9};
recurse.sum(arr, 0, 0, new int[0]);
for(int solution[] : recurse.solutions) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println("Solution: " + indices + "; " + vals);
}
}
Then it gives you:
Solution: arr[0], arr[1], arr[5] 12 + 3 + 9
Now, according to your requirements you don't want multiple values used, but it's not clear to me if you are only talking about not using the same array element more than once (ie a[i] can appear just once for each i in each solution) or you are talking about using the same number more than once (ie the number x can appear only once in each solution), or you are talking about using the same set of added numbers more than once (the solution x,y,z can appear just once). If you want to handle the other cases, such as to prevent solutions with duplicate values then just check the existing solutions before adding another. Using a HashSet is ideal for this:
public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();
ArrayList<int[]> duplicates = new ArrayList<int[]>();
HashSet<ArrayList<Integer>> solutionSet = new HashSet<ArrayList<Integer>>();
public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not
//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last
if(added == target) {
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
ArrayList<Integer> solution = new ArrayList<Integer>();
for(int i : next) {
solution.add(arr[i]);
}
Collections.sort(solution);
if(!solutionSet.contains(solution)) {
solutionSet.add(solution);
solutions.add(next);
} else {
duplicates.add(next);
}
}
} else if(added <= target) {//this assumes all array values are positive, if negative allowed, then no "if(added < target)" here
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}
public static void main2(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int[0]);
}
public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 3, 9};
recurse.sum(arr, 0, 0, new int[0]);
for(int i = 0; i < 2; i++) {
String label = i == 0 ? "Solution: " : "Duplicate: ";
ArrayList<int[]> solutionList = i == 0 ? recurse.solutions : recurse.duplicates;
for(int solution[] : solutionList) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println(label + indices + "; " + vals);
}
}
}
}
Which gives:
Solution: arr[0], arr[5], arr[6]; 12 + 3 + 9
Duplicate: arr[0], arr[1], arr[6]; 12 + 3 + 9
