If I understand the problem correctly, then what you are basically trying to do is group numbers so that the sum is 4 , and you give priority to adding numbers to the queue first.
You can do this using a dynamic programming approach. I am using int[] and int as a sum here, but the problem can be generalized to work with most datastructures.
First you must define a comparator that compares index lists, for example, lexicographical:
public class LexComp<T extends Comparable<T>> implements Comparator<List<T>> { @Override public int compare (List<T> la, List<T> lb) { Iterator<T> ita = la.iterator(); Iterator<T> itb = lb.iterator(); while(ita.hasNext() && itb.hasNext()) { T ea = ita.next(); T eb = itb.next(); int cr = ea.compareTo(eb); if(cr != 0x00) { return cr; } } if(itb.hasNext()) { return 1; } else if(ita.hasNext()) { return -1; } return 0; } }
Further you can use the following method:
public ArrayList<Integer> groupSum (int[] values, int sum) { ArrayList[] memory = new ArrayList[sum+1]; memory[0] = new ArrayList<Integer>(); LexComp<Integer> lc = new LexComp<Integer>(); int index = 0; for(int val : values) { for(int i = sum-val; i >= 0 ; i--) { if(memory[i] != null) { ArrayList<Integer> tmp = (ArrayList<Integer>) memory[i].clone(); tmp.add(index); if(memory[i+val] == null || lc.compare(tmp,(ArrayList<Integer>) memory[i+val]) < 0) { memory[i+val] = tmp; } } } index++; } return memory[sum]; }
This method returns ArrayList<Integer> indexes whose corresponding elements will be summed up to sum and null if such a group cannot be created. It will give priority to some groups according to the LexComp comparator.
For this input:
groupSum(new int[] {1,2,2,4,1,1},4); groupSum(new int[] {1,2,3,2,2,2},4); groupSum(new int[] {1,2,2,3},4); groupSum(new int[] {1,2,2,3,1},4);
This leads to:
[0, 1, 4] [0, 2] [0, 3] [0, 1, 4]
So, you must select the first, second and fifth elements that really add up to 4 . Then you have to remove these elements from the array yourself and repeat the process. In the event that such a sum cannot be built or there are not enough elements to sum up to 4 - as mentioned earlier - the algorithm will return null . In this case, you need to invent a backup mechanism. Perhaps the return of the group differs from sum smallest.
Background
This is a dynamic programming approach. You create a memory that stores - for each sum - the best solution found. Initially, we did not see any values, so all elements contain null except memory[0] , which contains an empty arraylist (because the sum of the null elements is 0 ). Thus, the memory looks like this:
Mem 4 -> null 3 -> null 2 -> null 1 -> null 0 -> []
The algorithm now iterates over the values. The first value we come across as an example is 1 . Now we are looking for lists that are already defined, and a single memory[0] . We can update this list in the list [0] (storage indexes of arrays), the sum of which is expressed in 1 . Since at this moment the value for this list is null , there is no alternative, so we add this list to memory[1] :
Mem 4 -> null 3 -> null 2 -> null 1 -> [0] 0 -> []
Next element 2 : we can update the two lists [] -> [1] and [0] -> [1] , this will lead to lists with the sums of 2 and 3 respectively, so we save them by these memory indices:
Mem 4 -> null 3 -> [0,1] 2 -> [1] 1 -> [0] 0 -> []
The next item will again be 2 . Now we can update lists 4 : [] -> [2] , [0] -> [0,2] , [1] -> [1,2] and [0,1] -> [0,1,2] . The first problem is that the sum [0,1,2] is 5 , which is higher than sum . This is not interesting, so we throw this one. However, the problem is that some of the places already contain lists:
Mem 4 -> null 3 -> [0,1] <> [0,2] 2 -> [1] <> [2] 1 -> [0] 0 -> []
For conflicting lists, we need to look for permission. In this case, the comparator - in this case, LexComp fixes the errors. Since we do this lexicographically, [0,1] benefits from [0,2] and [1] from [2] . After permission, the lists look like this:
Mem 4 -> [3] 3 -> [0,1] 2 -> [1] 1 -> [0] 0 -> []
The next element is 4 . The only list we can update so that the sum is less than or equal to sum is [] -> [3]
Mem 4 -> [3] 3 -> [0,1] 2 -> [1] 1 -> [0] 0 -> []
Next item 1 . We can update all lists except one 4 -> [3] (otherwise the sum will be more than 4 ). But again, this leads to many conflicts:
Mem 4 -> [3] <> [0,1,4] 3 -> [0,1] <> [1,4] 2 -> [1] <> [0,4] 1 -> [0] <> [4] 0 -> []
Now, if we run a lexicographic comparator, it will sometimes accept new lists, and sometimes old lists. After permission, the memory looks like this:
Mem 4 -> [0,1,4] 3 -> [0,1] 2 -> [0,4] 1 -> [0] 0 -> []
Now our current best solution for generating a group that sums up to four has changed from [3] to [0,1,4] . Finally, the last element 1 will not greatly change the game:
Mem 4 -> [0,1,4] <> [0,1,5] 3 -> [0,1] <> [0,4,5] 2 -> [0,4] <> [0,5] 1 -> [0] <> [5] 0 -> []
What after permission reads:
Mem 4 -> [0,1,4] 3 -> [0,1] 2 -> [0,4] 1 -> [0] 0 -> []
Now we have examined all the elements and the best solution for generating 4 is memory[4] or [0,1,4] .
Different order
This approach can be generalized in the sense that providing another Comparator on a List<T> (here LexComp<T> ) will give priority to another array of indices. The comparator should always fulfill at least the transitivity constraint: if x is less than y and y is less than z: x must be less than z. In addition, the list of indexes will always increase. Thus, an array of indices [4,1,0] impossible.