Print all combinations of length X using recursion

Question

EXAMPLE

Given an array [1,2,3] or [1,2,3,4] ,print all unique combinations for length 3.

CODE

public class PrintCombo {

    public void printCombo(int [] a, int [] buffer, int startIndex, int bufferIndex){

        printArray(buffer);

        if(buffer.length == bufferIndex){
            System.out.println();
            System.out.println("SOLUTION START");
            printArray(buffer);
            System.out.println("SOLUTION END");
            System.out.println();
            return;
        }
        if(startIndex == a.length){
            return;
        }

        for(int i = startIndex; i<a.length; i++){
            buffer[bufferIndex] = a[i];
            printCombo(a,buffer,i+1,bufferIndex+1);
        }
    }

    public void printArray(int [] buffer){
        for(int i = 0; i<buffer.length; i++){
            System.out.print(" "+buffer[i]);
        }
        System.out.println();
    }
}

OUTPUT

For array [1,2,3] ==> 1,2,3

For array [1,2,3,4] ==> 1,2,3 || 1,2,4 || 1,3,4 || 2,3,4

Problem

I have spent 3 hours tracing the code using a debugger and I am still struggling to understand how the recursive logic is working.

For instance, let's take an example when the array is [1,2,3].

1. PrintCombo(a, buffer, 0, 0)
2. buffer[0] gets updated to 1
3. We call PrintCombo(a, buffer, 1, 1)
4. buffer[1] gets updated to 2
5. We call PrintCombo(a, buffer, 2, 2)
6. buffer[2] gets updated to 3
7. We call PrintCombo(a, buffer, 3, 3)
8. Since buffer.length == bufferIndex we call printArray.
9. We return to the previous call

This is where I get lost. How does the stack make previous calls? I am trying hard to understand this approach thoroughly as I do not like memorizing solutions.

I decided to edit my code by adding a print statement to see what is inside the buffer at every iteration. Here is what I printed for example a = [1,2,3] and buffer size is 3.

 0 0 0
 1 0 0
 1 2 0
 1 2 3

SOLUTION START
 1 2 3
SOLUTION END

 1 3 3
 2 3 3
 2 3 3
 3 3 3

Answer 1

When initially called the for loop in printCombo will in each iteration set the first element of buffer to all possible values:

[1,-,-]    // i = 0, first iteration
[2,-,-]    // i = 1, second iteration
[3,-,-]    // i = 2, ...
[4,-,-]    // i = 3, ...

For each of these iterations there is a recursive call to printCombo to create all possible combinations for the remaining elements in buffer. E.g. in the first iteration [1,_,_] is passed to printCombo, whose for loop will now set the second element too all possible values:

[1,2,-]    // i = 0, first iteration in first recursive call to printCombo
[1,3,-]    // i = 1, second iteration in first recursive call to printCombo
[1,4,_]    // i = 2, ...

The process continues until either buffer is full (first if condition) or the pool of possible values is exhausted (second ifcondition). In the first case a candidate is found and printed. In the second case a dead end is reached.

Here is the evolution of buffer over time where the level of indention corresponds to the depth of recursion (a = [1,2,3,4] and buffer size 3):

[1,-,-]       
  [1,2,-]     
    [1,2,3]   // buffer.length == bufferIndex -> printArray
    [1,2,4]   // buffer.length == bufferIndex -> printArray
  [1,3,-]   
    [1,3,4]   // buffer.length == bufferIndex -> printArray
  [1,4,-]     // startIndex == a.length -> return 
[2,-,-]   
  [2,3,-]   
    [2,3,4]   // buffer.length == bufferIndex -> printArray
  [2,4,-]     // startIndex == a.length -> return
[3,-,-]   
  [3,4,-]     // startIndex == a.length -> return
[4,-,-]       // startIndex == a.length -> return

Answer 2

You can consider this approach: Every combination is a result of removing a value from the initial array until the desired length is reached.

if you take this array as an example [1, 2, 3, 4, 5], you would first remove 1 value at a time from it and get the following resulting arrays :

[2, 3, 4, 5]    //remove index [0]
[1, 3, 4, 5]    //remove index [1]
[1, 2, 4, 5]    //remove index [2]
[1, 2, 3, 5]    //remove index [3]
[1, 2, 3, 4]    //remove index [4]

From each one of them, you can then remove one value to reach your desired length of 3. [2, 3, 4, 5] would then give you the following arrays

[3, 4, 5]    //remove index [0]
[2, 4, 5]    //remove index [1]
[2, 3, 5]    //remove index [2]
[2, 3, 4]    //remove index [3]

And so on... Note that this will generate duplicate arrays, so my suggestion would be to either pass the final array by reference (an object in java) and check if the result already is in the array before you add it or return the whole resulting array and remove the duplicates after the array is generated. (first one would be more memory efficient though)