I think that all algorithms which can be solved with recursion can also be solved with stacks instead of recursion (see solution below). But very often it is easier to solve the problems with recursion before attempting the stack based solutions.
My recursive take on this problems would be in Java something like this:
public static void printCombinations(int[] array, int pos, int sum, int[] acc) {
if (Arrays.stream(acc).sum() == sum) {
System.out.println(Arrays.toString(acc));
}
for (int i = pos + 1; i < array.length; i++) {
int[] newAcc = new int[acc.length + 1];
System.arraycopy(acc, 0, newAcc, 0, acc.length);
newAcc[acc.length] = array[i];
printCombinations(array, i, sum, newAcc);
}
}
This function you can call like this:
printCombinations(new int[]{1, 3, 2, 2, 25}, -1, 3, new int[]{});
And it will print this:
[1, 2]
[1, 2]
[3]
Basically it goes through all possible sets in this array and then filters those out which have the sum of 3 in this case. It is not great, there are for sure better, more efficient ways to do this. But my point here is simply to show that you can convert this algorithm to a stack based implementation.
Here it goes how you can implement the same algorithm using stacks instead of recursion:
public static void printCombinationsStack(int[] array, int sum) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
while (true) {
int i = stack.peek();
if (i == array.length - 1) {
stack.pop();
if (stack.isEmpty()) {
break;
}
int last = stack.pop();
stack.push(last + 1);
} else {
stack.push(i + 1);
}
if (stack.stream().map(e -> array[e]).mapToInt(Integer::intValue).sum() == sum) {
System.out.println(stack.stream().map(e -> Integer.toString(array[e]))
.collect(Collectors.joining(",")));
}
}
}
This method can be called like this:
printCombinationsStack(new int[]{1, 3, 2, 2, 25}, 3);
And it outputs also:
1,2
1,2
3
How I came to this conversion of a recursive to a stack based algorithm:
If you observe the positions in the acc array on the first algorithm above, then you will see a pattern which can be emulated by a stack. If you have an initial array with 4 elements, then the positions which are in the acc array are always these:
[]
[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 3]
[0, 2]
[0, 2, 3]
[0, 3]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]
There is a pattern here which can easily be emulated with stacks:
The default operation is always to push into the stack, unless you reach the last position in the array. You push first 0 which is the first position in the array. When you reach the last position of the array, you pop once from the array and then pop again and a second popped item which you push back to the stack - incremented by one.
If the stack is empty you break the loop. You have gone through all possible combinations.
