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

Dever

Are you required to use recursion to solve this problem? – Ishmael

@TimBiegeleisen Yes. I know we can solve it alternatively but i am really trying to understand recursive approaches for my own good. – Dever

Recursive approaches aren't used so often since most loops are more easily debuggable and are less likely to go infinite, but they generally work like this: 1. guard statements that check for exit conditions. 2. logic that results in one or more calls to the same method with updated parameters that work towards one or more conditions present in the guard statements – Regardful

@AustinSchäfer yup i get it in theory but i am having particular trouble with tracing the above problem, would appreciate if you can help with the tracing of it. – Dever

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

Siloxane

I understand the overall objective of code, that is to recursively generate all unique combinations. However i am having trouble having understanding the recursive part in particular so i would appreciate it if you can take one of the examples and trace it step by step. – Dever

The objective of the recursive call in this approach is to ask the function if a combination is possible with the given value from the initial array. The subarrays [4, -, -] and [3, 4, -] would result in a dead end in this example and therefore would not be added to the displayed result. – Achitophel

** In my comment above, by value, I meant buffer – Achitophel

@Dinero, I added a trace indicating the values in buffer at each step through the execution – Siloxane

That makes sense, i decided to do a trace of what buffer looks like. I just edited my code and printed the output. It is slightly different than the trace you are explaining above. Am i missing something? – Dever

@Dinero, the only differences is in array elements marked with a dash in my answer. Those are 0 after acquiring buffer. Later when the buffer is ' reused' their value is what was last written to them but what is now irrelevant and will be overwritten while calculating the remaining elements for the current combination. You can convince yourself by modifying printArray to only print the first k elements and pass bufferIndex for k. This way the output will match exactly. – Siloxane

@Siloxane - just curious do you know why in the loop we start i = startIndex instead of i = 0 ? – Dever

startIndex points at the first remaining element in buffer. Or put differently, all elements before startIndex have been calculated already by previous recursive invocations. – Siloxane

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)

Achitophel