You have a list of House with position with either 0, 1, 2, 3, 4. Let me use a annotation of H{i} to represent a House with position i which 0 <= i <= 4.
If your input list is
[ H{0}, H{1}, H{2}, H{3}, H'{3}, H{4}, H'{4} ]
which H' is another house
the result is
[
[ H{0}, H{1}, H{2}, H{3}, H{4} ],
[ H{0}, H{1}, H{2}, H{3}, H'{4} ],
[ H{0}, H{1}, H{2}, H'{3}, H{4} ],
[ H{0}, H{1}, H{2}, H'{3}, H'{4} ],
]
This give me following information:
- When iterate to
H{3}, it find a House with next position, i.e. 4.
- When iterate to
H{4}, it will create the 1st list and store the houses with a position of 0, 1, 2, 3 iterated previously.
- After reach
H{4}, it will find another House with position 4, i.e. H'{4}, and create 2nd list and store the houses iterate previously except H{4}.
- When reach the end of the list, it is back to
H'{3} and iterate the list again to create 3rd and 4th list.
From #2, we know that:
- We need to create a list to store the
House if house position = 4
- There should be a
buffer to store the House with position 0, 1, 2, 3, iterated before. buffer[0] will store H{0}, buffer[1] will store H{2}, etc.
From #3, we know that:
If reach House with position 4, the list will further iterate until reach the end of the list.
We can have a base function as follows:
public static List<House[]> foo(House[] houses, List<House> buffer) {
List<House[]> list = new ArrayList<House[]>();
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
if (house.getPosition() == 4) {
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
}
}
}
return list;
}
What the above do?
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
At the very beginning, buffer is empty with size = 0. If it find a House with position 0, it will be stored into the buffer and the buffer size becomes 1. When the list iterate to next House with position = 1 (the buffer size), it will be stored. Otherwise, find another House that match the condition.
if (house.getPosition() == 4) {
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
}
As mentioned, a list will be created to store the House in the buffer if there is a House with position 4. buffer.remove(buffer.size() - 1) is to remove the last House with position 4 such that another House can be stored into buffer.
So far, no recursive call is in our function since the case for House with position 4 do not need it.
Let's look back to #1 and #4. We know that:
If reach a House with position other than 4, it find a House with next position and create a list when iterate to House with position 4.
It means that our base function will be called if a House with position other than 4. So, we can modify our function as follows:
public static List<House[]> foo(House[] houses, List<House> buffer) {
List<House[]> list = new ArrayList<House[]>();
for (House house : houses) {
if (house.getPosition() == buffer.size()) {
buffer.add(house);
if (house.getPosition() == 4) { // base case, no recursive call
list.add(buffer.toArray(new House[buffer.size()]));
buffer.remove(buffer.size() - 1);
} else { // recursive case
list.addAll(foo(houses, buffer));
}
}
}
if (buffer.size() > 0) {
buffer.remove(buffer.size() - 1);
}
return list;
}
In summary, we have 2 case for the problem. One is the base case to handle House with position 4 and another case is to handle House with position other than 4 which need a recursive call.
Recursive function normally divide problem into cases. The function calls itself recursively on a smaller list of Houses until reaching the base case. Hope this can help.
